Selection sort

iissaacc·2022년 1월 19일
0

Prologue

Sorting을 공부하다보면 어떤 상황에서는 뭘써야 하는지 알게되면서 더 큰 알고리즘을 만들 때 도움이 될 거라고 기대하면서 몇가지를 정리하려고 한다. 그래서 우리가 알아야 하는 것은 크게 3가지다.

  1. 알고리즘
  2. 구현
  3. best and worst case

그리고 이건 앞으로 우리가 정렬할 array다.

Building block

selection sort는 array에서 가장 작은 수를 골라서 가장 앞으로 보내고 두번째로 작은 수를 골라서 두번째 자리로 보내는 방법으로 작동한다.

array에서 가장 작은 수를 찾는데 처음에는 어디에 있는지 모르니까 제일 앞에 있는 수를 골라서 순차적으로 비교한다.

1이 4보다 작으므로 가장 작은 수는 1로 바꾸고 뒤에 있는 숫자들과 차례대로 비교한다.

비교 결과 1이 array안에서 가장 작은 수이므로 1과 4의 자리를 바꾼다.

이제 첫번재 loop가 끝났다. array가 정렬할 때까지 이 작업을 반복하면 된다.

Think visually

앞서 array 안에서 가장 작은 수를 찾아서 가장 왼쪽으로 가져다놨다. 그래서 같은 작업을 두번째 index부터 하면 된다.

4를 골라서 오른쪽에 있는 수들과 비교하고

가장 작은 수는 2로 밝혀졌다.

두번째 loop에서 처음 골랐던 4와 자리를 바꾼다.

이 때 핵심은 처음 가장 작다고 생각하고 골랐던 수의 자리를 잊지 않는 것이다. 그래야 뒤에 정말 가장 작은 수가 튀어나왔을 때 처음 생각했던 수의 자리와 바꿀 수 있다.

Pseudo code

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 종료

Implementation

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

Best and worst case

selection sortbubble sort처럼 비교, 교환이 일어난다. 그렇지만 bubble sort와는 다르게 loop마다 교환이 한 번만 일어난다는 점이 장점으로 작용한다.

  • Best case: 정렬된 array
    비교만 n(n1)/2n(n-1)/2번 일어난다.

  • Worst case: 역순으로 정렬된 array
    비교 n(n1)/2n(n-1)/2번, 교환 (n1)(n-1)번 일어난다.

Epilogue

selection sortbubble sort사이에 한 가지를 써야 한다면 selection sort를 써야 한다. 두 알고리즘의 worst case를 비교해보면 잘 드러난다.

  • bubble sort: n2n^2
  • selection sort: (n+2)(n1)/2(n+2)(n-1)/2

이차항 이하는 다 떼버리면 n2n^2n2/2n^2/2사이에 뭘 쓸지 고르는 문제와 같아서 selection sortbubble sort보다 2배 빠르다.

0개의 댓글