[알고리즘] 선택 정렬(Selection Sort)

선택 정렬이란

선택해서 정렬하는 방식입니다. 예를 들면, 키 차이가 나는 사람들이 무작위 정렬해 있을 때 한번 쓱 훑어보고 키가 가장 작은 사람을 찾아 맨 앞으로 보냅니다. 그 다음 쓱 훑어봐서 두 번째로 작은 사람을 찾아 두번째에 배치합니다. 이 방법을 계속 반복하여 오름차순으로 정렬합니다.

 

선택 정렬 예

예) [4, 6, 2, 9, 1]

 

1단계 : [4, 6, 2, 9, 1]        #제일 작은 수 1을 찾아 4와 교체

              [1, 6, 2, 9, 4]

2단계 : [1, 6, 2, 9, 4]        #1을 제외한 제일 작은 수 2를 찾아 6과 교체

              [1, 2, 6, 9, 4]

3단계 : [1, 2, 6, 9, 4]        #2를 제외한 제일 작은 수 4를 찾아 6과 교체

              [1, 2, 4, 9, 6]

4단계 : [1, 2, 4, 9, 6]        #4를 제외한 제일 작은 수 6를 찾아 9과 교체

              [1, 2, 4, 6, 9]

 

모두 정렬이 되었습니다. 버블 정렬보다 훨씬 더 적은 비교를 하는 것 같지만, 실제로는 각 배열을 계속해서 탐색하는 방식이라 2중 반복문을 사용해야 합니다. 버블 정렬하고 다른 건 바로 "최솟값"을 찾아 변경하는 것입니다.

 

버블 정렬 python 코드

input = [4, 6, 2, 9, 1]

def selection_sort(array):
    N = len(array)
    for i in range(N):
        tmp = array[i]
        index = i
        for j in range(i+1,N):
            if array[j] < tmp:
                tmp = array[j]
                index = j
        array[i],array[index] = array[index], array[i]
    return array


selection_sort(input)
print(input) # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",selection_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",selection_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",selection_sort([100,56,-3,32,44]))

 

선택 정렬의 시간 복잡도

선택 정렬의 시간 복잡도도 O(N^2)만큼 걸립니다. 2중 for문을 사용했고, array의 길이 만큼 반복했습니다. 선택 정렬은 다음과 같이 동작합니다. 맨 왼쪽부터 최솟값을 찾아 정렬한다고 생각하시면 됩니다.

선택 정렬