Selection Sort: 선택 정렬

* Selection Sort?

출처: https://algorithms.tutorialhorizon.com/selection-sort-java-implementation/selection-sort-gif/

 

선택 정렬은 입력 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (숫자 개수 - 1)만큼 되풀이하면 전체 숫자들이 정렬된다.

 

* Pseudocode

선택 정렬의 슈도 코드

 

* 분석

 

선택 정렬은 2중 for문을 돌게 된다. 외부 for문은 n-1번 시행되며, 내부 for문은 0부터 n-2까지 변하는 i에 대하여 (n-1-i)번 반복 수행될 것이다. 실제 비교는 내부 for문에서 수행되는데 i가 0일 떄 n-1번, i가 1일 떄 n-2번 이런 식으로 비교하니까 총 비교 횟수는 (n -1) + (n - 2) +  ... + 1 = n ( n + 1) / 2가 되며 이것이 선택 정렬의 시간복잡도가 된다. 또한 한 번의 데이터 이동을 위해서 3번의 이동이 필요한데, (min, arr[i], tmp 이렇게 있다고 쳤을 때 tmp = min, min = arr[i], arr[i] = tmp)  따라서 총 이동 횟수는 3(n - 1)이 된다. 

선택 정렬의 장점은 자료 이동 횟수를 미리 알 수 있다는 점이다. 또한 간단하다.

단점은 이동 횟수가 크며 자료가 정렬된 경우에는 불필요하게 자기 자신과의 이동을 하게 된다. 따라서 이러한 문제를 해결하려면 자기 자신이(arr[i]) 최소값이라면 자료 이동을 하지 않게 코드를 추가해주면 된다.

                                                       if (i != least) 

                                                                SWAP(list[i], list[least], tmp);

 

또한 같은 값의 레코드가 여러 개 있는 경우 상대적인 위치가 변경될 수 있다는 단점도 있다. 

 

* 선택 정렬의 시간 복잡도는 O(n^2)