오늘은 선택 정렬 알고리즘에 대해 공부해 봅시다. selection sort는 매 회전마다, 제일 우선 순위가 높은 값을 선택해서 재정렬 하는 알고리즘입니다. 배열 arr의 크기가 n이라고 해 봅시다. 그러면 총 n회전을 돌 건데요. i회전일 때 이러한 일을 수행합니다. 구간 [i,n]에서 우선순위가 가장 높은 위치 lo를 찾습니다. 그리고 배열에서 i번째 원소와 lo번째에 있는 값을 맞바꿉니다. 구간 [i,n]은 정렬이 되어 있지 않기 때문에, 우선 순위가 가장 높은 값과 위치를 찾기 위해서, i에서부터 n까지 보아야 합니다. 그러므로, 회전마다 O(n-i)만큼 걸리게 되고, 결과적으로 시간 복잡도는 O(n^2)가 됩니다. 매 회전마다, O(log(n)) 급에 해결할 수 있는 방법이 있는데, 특수한 자료구조를 이용하면 가능합니다. 이는 자료구조 시간에 언급해 드리도록 하겠습니다.

 

 


 예제를 봅시다. 배열 arr = [2,5,1,2,4,7]이라고 해 봅시다. 저는, 오름차순으로 정렬할 겁니다. 즉, 우선 순위가 높을수록 원소의 크기는 작다고 보시면 됩니다. 먼저 1회전일 때 봅시다. 저는 파란색 구간에서 priority가 제일 높은 위치를 찾을 겁니다.

 

 

 오름 차순이기 때문에 파란색으로 칠한 구간 중, 제일 작은 값은 3번 위치에 있는 1입니다. 이것을 아래 그림에서, 노란색으로 표시해 보겠습니다.

 

 

 이것을 i번째 원소인, 그러니까 초록색으로 표시한 1과 바꿔야 합니다. 그러면 1과 2가 swap이 됩니다.

 

 

 이렇게 1회전이 끝나요. 보라색 부분은 제가 볼 필요가 없어요. 2회전일 때에는 파란색으로 표시한 구간만 보면 됩니다. 이 구간에서 우선 순위가 제일 높은 원소는 3번째에 있는 원소 2입니다. 물론 4번째에 있는 원소도 2인데요. priority가 제일 낮은 것들이 여러개 있을 때에는, 구간에서 제일 앞에 나온 것을 뽑았습니다.

 

 

 노란색으로 칠한 원소입니다. 이것이랑 초록색으로 칠한 것과 swap 하면 2회전이 끝납니다.

 

 

 그러면 [1,2] 구간에 있는 것들은 이미 sorting이 되었습니다. 3회전일 때에는 파란색으로 칠해진 구간에서 우선 순위가 제일 높은 원소를 찾으면 됩니다. 2인가요? 네. 제일 작은 것을 찾으면 되기 때문입니다. 그것을 노란색으로 표시해 보겠습니다.

 

 

 즉, 연두색하고 노란색 부분을 맞바꾸면 됩니다.

 

 

 3회전이 끝났습니다. 4회전일 때에는 어떻게 하면 될까요? 파란색으로 표시된 부분에서 제일 priority가 높은, 그러니까 제일 작은 원소를 찾으면 됩니다. 그 값은 4입니다. 그것과 연두색으로 칠한 5를 바꾸면 되겠습니다.

 

 

 표시를 하면 이 부분입니다. 연두색과 노란색을 swap 합니다.

 

 

 그러면 앞에 4개는 sorting이 되었습니다. 5회전일 때에는, 뒤에 2개 중에서 우선 순위가 제일 높은, 그러니까 제일 작은 원소를 뽑으면 되는데 그 값이 5입니다.

 

 

 바꿀 필요가 없어요. 왜냐하면, [5,6] 구간에 속해있는 원소들 중에서, 제일 작은 것은 5인데, 배열 arr에서 5번째 원소가 5이기 때문입니다. 이제 파란 부분만 보면 됩니다.

 

 

 파란 부분에서 제일 작은 원소는 7입니다. 6회전일 때인데요. 6번째에 있는 원소가 제일 작기 때문에, 6회전일 때에도 swap을 할 필요가 없음을 알 수 있습니다. 정렬이 끝났습니다.

 

 


 그러면 선택 정렬 알고리즘은 stable 할까요?

 

 

 배열 arr = [2, 2, 1, 2]라고 해 봅시다. 앞에 있는 2를 빨간색, 뒤에 있는 2를 노란 색으로 칠해 봅시다.

 

 

 1회전일 때, 빨간색으로 칠한 2와 1이 바뀝니다.

 

 

 그 다음에 2, 3, 4회전에서 원소의 순서가 바뀌지 않아요. 최종적으로 노란색 2 뒤에 빨간색 2가 오게 되었습니다. 빨간색과 노란색은 우선 순위가 같았습니다. 그렇지만 순서가 정렬 전과 정렬 후에 바뀌었습니다. 원래 빨간색에서 노란색 순서대로 갔는데, 정렬하고 나서 보니까 노란색에서 빨간색 순으로 가게 되었습니다.

 

 그렇기 때문에 선택정렬은 stable하지 않습니다.