Sorting을 공부하다보면 어떤 상황에서는 뭘써야 하는지 알게되면서 더 큰 알고리즘을 만들 때 도움이 될 거라고 기대하면서 몇가지를 정리하려고 한다. 그래서 우리가 알아야 하는 것은 크게 3가지다.
그리고 이건 앞으로 우리가 정렬할 array다.
selection sort
는 array에서 가장 작은 수를 골라서 가장 앞으로 보내고 두번째로 작은 수를 골라서 두번째 자리로 보내는 방법으로 작동한다.
array에서 가장 작은 수를 찾는데 처음에는 어디에 있는지 모르니까 제일 앞에 있는 수를 골라서 순차적으로 비교한다.
1이 4보다 작으므로 가장 작은 수는 1로 바꾸고 뒤에 있는 숫자들과 차례대로 비교한다.
비교 결과 1이 array안에서 가장 작은 수이므로 1과 4의 자리를 바꾼다.
이제 첫번재 loop가 끝났다. array가 정렬할 때까지 이 작업을 반복하면 된다.
앞서 array 안에서 가장 작은 수를 찾아서 가장 왼쪽으로 가져다놨다. 그래서 같은 작업을 두번째 index부터 하면 된다.
4를 골라서 오른쪽에 있는 수들과 비교하고
가장 작은 수는 2로 밝혀졌다.
두번째 loop에서 처음 골랐던 4와 자리를 바꾼다.
이 때 핵심은 처음 가장 작다고 생각하고 골랐던 수의 자리를 잊지 않는 것이다. 그래야 뒤에 정말 가장 작은 수가 튀어나왔을 때 처음 생각했던 수의 자리와 바꿀 수 있다.
1. array의 index를 다 돌때가지 반복
2. index 순서대로 가장 작은 수로 지정
3. 2에서 정한 index이후부터 남은 index까지 반복
4. index 순서대로 2에서 정한 값과 비교
4-1. 2의 값보다 4의 값이 작으면
4-2. 가장 작은 값의 index 교체
5. 3번 loop 종료
6. 3과 4-2가 다르면
7. 4-2의 수와 2의 수 교체
8. 1번 loop 종료
def selection_sort(array):
for i in range(len(array)-1):
lowest = i
for j in range(i+1, len(array)):
if array[lowest] > array[j]:
lowest = j
if lowest != i:
array[i], array[lowest] = array[lowest], array[i]
return array
selection sort
도 bubble sort
처럼 비교, 교환이 일어난다. 그렇지만 bubble sort
와는 다르게 loop마다 교환이 한 번만 일어난다는 점이 장점으로 작용한다.
Best case: 정렬된 array
비교만 번 일어난다.
Worst case: 역순으로 정렬된 array
비교 번, 교환 번 일어난다.
selection sort
와 bubble sort
사이에 한 가지를 써야 한다면 selection sort
를 써야 한다. 두 알고리즘의 worst case를 비교해보면 잘 드러난다.
이차항 이하는 다 떼버리면 와 사이에 뭘 쓸지 고르는 문제와 같아서 selection sort
가 bubble sort
보다 2배 빠르다.