[알고리듬] #74 선택 정렬

[key word] 픽업, 소트 메소드, 리버스

파이썬 실습창을 열 수 있습니다.실습창 열기

 

 

선택 정렬

 

1. 선택 정렬 분석

선택 정렬(selection sort)도 버블 정렬과 함께 기본적인 정렬방법입니다.

다음 코드를 분석하여 원리를 파악하여 보세요.

a=[1,5,2,4,3]
n=len(a)
for i in range(n-1):
    p=i
    for j in range(i+1,n):
        if a[p]>a[j]:p=j
    a[i],a[p]=a[p],a[i]
print(a)

 

• 선택 정렬의 원리를 개략적으로 설명할 수 있습니까?
  첫째 칸에 전체의 최소값을 넣는다.
  다음 칸에 나머지의 최소값을 넣는다.
  이러한 방법으로 마지막 앞의 칸까지 진행한다(마지막은 자동으로 최대값)
• 3번 줄에 있는 i의 역할은 무엇입니까?
  값을 넣을 칸의 인덱스 역할을 합니다.
  왼쪽부터 한 칸씩 오른쪽으로 이동합니다.
• 4번 줄 p는 무슨 일을 합니까?
  최소 값이 있는 칸의 인덱스입니다.
  값을 넣을 곳(i)에 있는 값이 최소라고 가정합니다.
• 5번과 6번 줄은 어떤 일을 합니까?
  넣을 곳(i) 다음에 있는 값들 중에서 최소값이 있는 곳의 인덱스를 찾아서 p에 기억시킵니다.
  p에는  진행된 것 중에서 최소값이 있는 곳의 인덱스가 있게 됩니다.
  p는 임의의 변수입니다(pivot에서 따왔습니다).
• 7번 줄은 어떤 일을 합니까?
  값을 넣을 곳(i)과 최소값이 있는 곳(p)을 바꾸어 기억시킵니다.
• 내림차순 정렬은 어떻게 합니까?
  6번 줄의 부등호를 바꾸어 최대값을 찾아서 기억시켜 나가면 됩니다.

차례차례 최소값을 선택(selection)하여 정렬합니다.

그래서 선택 정렬이라고합니다.

다르게 표현하면 최소값을 콕집어서(pick up) 정렬합니다.

그래서 별명이 픽업 정렬(pick-up sort)입니다.

 

2. 선택 정렬 사용

사랑스러운’이라는 뜻의 영어 단어는‘lovable'입니다.
이 단어에 있는 알파벳을 오름차순으로 정렬(ascending sort)하면 'abellov'이 됩니다.
내림차순으로 정렬(descending sort)하면 'volleba'이 됩니다.

 

mamihlapinatapai (마밀라피나타파이)
이 단어는 전 세계에서 뜻이 가장 긴 단어로 1933년 기네스북에 등재.되었습니다.

칠레 남부 야간족(Yaghan) 언어인데 뜻은 다음과 같다고 합니다.

'서로에게 꼭 필요한 것이면서도,
 자신이 굳이 하고 싶지 않은 어떤 일에 대해서,
 상대방이 자원하여 하여 주기를 바라면서,
 두 사람 사이에 말없이 긴급하게 오가는 미묘한 눈 빛'

 

이 단어에 있는 알파벳을 선택 정렬 방법으로 내림차순 정렬하여 보세요.

word='mamihlapinatapai'
a=list(word) 
n=len(a)
for i in range(n-1):
    p=i
    for j in range(i+1,n):
        if a[p]<a[j]:p=j
    a[i],a[p]=a[p],a[i]
w=''.join(a)
print(w)

'''
결과입니다.
tppnmmliiihaaaaa

2번 줄에 있는 a의 모습입니다.
['m', 'a', 'm', 'i', 'h', 'l', 'a', 'p', 'i', 'n', 'a', 't', 'a', 'p', 'a', 'i']

9번 줄은 a의 아이템(item)을 결합(join)합니다.
결합은 null string(아무것도 없는 것)으로 합니다.
'''

 

문자열의 sort  method를 사용하면 다음과 같이 코딩할 수 있습니다.

결과는 같습니다.

word='mamihlapinatapai'
a.sort(reverse=True)  #내림차순, reverse 생략하면 오름차순)
w=''.join(a)
print(w)

  

 

수고하셨습니다.

안녕!