선택 정렬 (Selection Sort)

선택된 값과 나머지 데이터들을 전부 비교하여 알맞은 자리를 찾는 방법이다.

시간 복잡도

Best - O(N^2)

Average - O(N^2)

Worst - O(N^2)

설명

출처 https://developpaper.com/look-at-the-animation-algorithm-sort-select-sort/

길이가 n인 배열에서 인덱스가 0번인 자리를 선택하고, 해당 인덱스를 최솟값을 가지는 인덱스로 둔다. 그 후에 배열의 끝까지 탐색하며 최솟값을 가지는 인덱스를 찾는다.

 

탐색이 완료되면, 선택한 인덱스 0번의 요소와 최솟값을 맞바꾼다.

 

이후 인덱스가 1번인 자리를 선택하고 그 이후의 요소들을 가지고(이전 인덱스는 이미 정렬했기 때문에 탐색하지 않는다.) 최솟값을 탐색한 다음 다시 최솟값을 맞바꾼다.

 

이를 n - 1번 반복하면 오름차순 정렬이 완료된다.

구현(파이썬)

arr = [29, 10, 14, 37, 20, 25, 44, 15]

for i in range(len(arr) - 1):
    minIndex = i
    for j in range(i, len(arr)):
        # 오름차순 기준, 내림차순은 부호를 반대로
        if arr[minIndex] > arr[j]:
            minIndex = j
    arr[i], arr[minIndex] = arr[minIndex], arr[i]
    print(arr)