[06정렬] 6-1 선택 정렬 (p156~p160)

[정렬 알고리즘 개요]

• 정렬: 데이터를 특정한 기준에 따라서 순서대로 나열하는 것.
• 정렬은 이진 탐색의 선행조건임. 이진 탐색을 위해선 정렬이 필수적으로 선행 되어야 함.
• 선택, 삽입, 퀵, 계수 정렬 등이 있음.

 

[선택 정렬]

• 위와 같이 데이터가 무작위로 있을 때, 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다.
• 가장 원시적인 방법
• 매번 '가장 작은 것을 선택'한다는 의미에서 '선택 정렬'이라고 함.

[선택 정렬 시각화]

step0) 초기 단게에서는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택한다. 따라서 '0'을 선택해 맨 앞에 있는 데이터 '7'과 바꾼다.

 

 

step1) 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '5'와 바꾼다.

 

 

step2) 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '2'를 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꾼다.

 

 

step3) 이제 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중에서 가장 작은 데이터인 '3'을 선택한다. 이를 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '7'과 바꾼다.

 

 

step8)

 

 

step9) 가장 작은 데이터를 앞으로 보내는 과정을 9번 반복한 상태는 다음과 같으며 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 이 단계에서 정렬을 마칠 수 있다.

 

[소스 코드]

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)):
    min_index = i #가장 작은 원소의 인덱스
    for j in range(i+1, len(array)):
        if array[min_index] > array[j]:
            min_index = j

        array[i], array[min_index] = array[min_index], array[i]

print(array)

 

 

['스와프' 개념]

• 스와프란 특정한 리스트가 주어졌을 때 두 변수의 위치를 변경하는 작업을 의미.

array = [3, 5]
array[0], array[1] = array[1], array[0]

print(array)

• array[1]과 array[0]은 각각 5와 3이므로, (5, 3)이 array[0] 자리와 array[1]자리에 각각 대입됨.

• 파이썬에서는 리스트 내 두 원소의 위치를 변경 가능하나, 다른 언어의 경우 아래와 같이 tmp 필요함.

a = 3
b = 5

tmp = a
a = b
b = tmp

print("바뀐 a와 b는 각각", a, b)