[Python][이코테] 선택 정렬

선택정렬은 말 그대로 '선택해서 정렬한다' 라고 할 수 있다.

 

예를들어

7 5 9 0 3 1 6 2 4 8

이라는 숫자의 모음이 있다.

 

이를 오름차순으로 정렬하고 싶을때 파이썬에서는 단순히 sort()를 사용하면 해결된다.

 

하지만 그래도 우리는 알고리즘을 공부하는 사람으로서 메서드에 의존할 것이 아닌 직접 코드로 구현할 줄 알아야한다.

 

---

선택 정렬의 알고리즘은 단순하다.

 

오름차순의 경우

'가장 작은 숫자를 찾아서 맨 앞에 두고, 그 다음 숫자를 찾아서 그 다음에 두고...' 를 반복한다.

 

7 5 9 0 3 1 6 2 4 8

에서

 

0 5 9 7 3 1 6 2 4 8

0을 찾아 7과 바꾸고

 

0 1 9 7 3 5 6 2 4 8

그 다음 1을 찾아 2번째 자리인 5와 바꾸는 식으로

 

가장 작은 숫자를 하나씩 찾아서 앞과 바꿔 준다.

 

# 6-1 정렬 선택 정렬

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] #swap
    
print(array)

7: i + 1 부터 array의 수 만큼 반복문을 실행한다.

    여기서 i + 1인 이유는 i 번째 index가 바꿔줘야 할 대상이기 때문이다.

9: min_index = j로 가장 작은 숫자가 있는 index번호를 min_index에 저장한다.

 

11: array[i], array[min_index] = array[min_index], array[i] <- 스와프

    아마 다른 언어를 공부해본 사람들은 알것이다. 버블정렬이라는 것을

 

int a = 10;
int b = 3;

int temp = a;
a = b;
b = temp;

위와 같은 방법으로 a와 b의 값을 바꾸듯이

 

파이썬은 단순히 바꿔줄 수 있다.

---

정리하자면 선택정렬은 하나하나 전부 찾아서 바꿔주기 때문에 단순히 빠른 정렬이라고 할 수 없다.

 

하지만 코딩테스트를 하다보면 리스트에서 가장 작은 값을 찾는일이 자주 있으므로 알고 있으면 좋다.

 

min()쓰면 되는데

참고로 위의 코드는 for 반복문이 두 번 사용되었으므로 시간복잡도는 $O(N^2)$이다.