1. 설명
선택 정렬은 무작위로 된 데이터에서 가장 작은 값을 찾아 차례대로 정렬하는 알고리즘입니다.
사진 출처: https://github.com/GimunLee
-
무작위로 된 데이터에서 첫 번째 인덱스를 선택하고, 첫 번째 인덱스의 값을 최솟값으로 선언합니다.
-
두 번째 인덱스의 값과 최솟값으로 정의된 값을 비교합니다.
1) 두 번째 인덱스의 값이 최솟값보다 클 때, 두 번째 인덱스에서 세 번째 인덱스로 이동합니다.
2) 두 번째 인덱스의 값이 최솟값보다 작을 때, 최솟값을 두 번째 인덱스의 값으로 선언합니다. -
세 번째 인덱스의 값과 최솟값으로 정의된 값을 비교합니다.
1) 세 번째 인덱스의 값이 최솟값보다 클 때, 세 번째 인덱스에서 네 번째 인덱스로 이동합니다.
2) 세 번째 인덱스의 값이 최솟값보다 작을 때, 최솟값을 세 번째 인덱스의 값으로 선언합니다. -
위의 과정을 반복하고, 첫 번째 인덱스의 값과 최솟값으로 정의된 값을 바꾸어 줍니다.
-
다음으로 두 번째 인덱스를 선택하고, 위의 과정을 반복하여 줍니다.
해당 알고리즘은 구현이 쉬운 반면 시간 복잡도(O(n^2)) 측면에서는 상당히 효율적이지 않습니다. 그리고 무작위로 된 데이터 내에 동일한 값이 있을 때, 상대적인 위치가 변경될 수 있으므로 불안정 정렬입니다.
2. 코드
for i in range(len(array)):
minIdx = i
for j in range(i+1, len(array)):
if array[minIdx] > array[j]:
minIdx = j
array[i], array[minIdx] = array[minIdx], array[i]