배열의 크기가 n일 때, O(n2)로 동작하는 몇 개의 정렬 알고리즘이 있습니다. 선택 정렬, 삽입 정렬, 버블 정렬이 대표적입니다. 이 글에서는 선택 정렬을 알아봅니다. 이 셋 중, 자주 보이는 알고리즘은 insertion sort인데요. 아래 글을 참고하시면 좋습니다.
- insertion sort에 대해서 알아봅시다. 링크
선택 정렬은 어떻게 동작하는가?
selection sort는 정수를 오름차순으로 정렬한다고 하였을 때, 아래와 같이 동작합니다.
- i번째 cycle일 때
- i번째 원소 a와 [i+1, n] 구간에 있는 원소 중 가장 작은 원소 b와 비교합니다.
- a가 b보다 크면, a와 b를 바꿉니다.
이것이 무슨 소리인가? 아래 그림을 봅시다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select4.png)
배열 arr에 2, 1, 4, 7, 5 순서대로 저장되어 있습니다. 저는 이 배열을 오름차순으로 정렬하려고 합니다. 배열의 크기 n은 5입니다. 1번째 cycle이 돌 때 아래와 같은 일이 일어납니다.
- 1번째 원소인 2
- [2, 5] 구간에 있는 원소 중 가장 작은 원소를 구합니다.
[2, 5] 구간에 있는 원소 중 가장 작은 원소는 1입니다. 제가 파란색으로 표시한 원소입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select5.png)
a가 2이고 b가 1입니다. a가 b보다 큰 상황인가요? 고로 두 원소를 바꿉니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select6.png)
그러면, 1, 2, 4, 7, 5가 되고 사이클 1이 끝납니다. 이제, 보라색 구간은 정렬 완료되었습니다. 사이클 2로 가 볼까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select7.png)
2번째 원소인 2와, 회색 구간에 있는 수 중 가장 작은 수를 뽑습니다. 회색 구간에 있는 것 중 가장 작은 것은 4입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select8.png)
2 < 4인가요? 따라서 원소가 바뀌지 않습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select9.png)
이렇게 사이클 2가 완료됩니다. 이런 식으로 사이클을 n-1번 돌면 정렬이 완료되는 것이 선택 정렬입니다. 시간 복잡도는 어떻게 될까요? i번째 사이클에 정렬되지 않은 n-i개의 원소 중 최소값을 고르는 연산을 하게 되므로, O(n2)가 됩니다.
정당성 증명해 보기
이 알고리즘이 정렬을 올바르게 할까요? 이걸 증명하기 위해서는 아래를 증명해야 합니다. n개의 정수로 이루어진 배열을 선택정렬로 오름차순 정렬할 때
- i번째 cycle에 i번째 요소에 업데이트 되는 요소는 아래 조건을 만족합니다.
- a1은 가장 작은 수이다.
- ai-1 < ai이거나 ai-1 = ai이다.
1번째는 자명합니다. 2번째가 문제입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select10.png)
i번째 사이클이 돌 때 상황을 생각해 봅시다. 이 경우에는
- 노란색으로 표시한 원소
- 회색 부분 중, 제일 작은 원소
이 둘 중 가장 작은 것이 i번째 사이클이 끝났을 때 a[i]에 오게 됩니다. 즉, i번째 사이클이 끝난 이후 상황은 아래와 같이 됩니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select11.png)
a[i]는 회색으로 표시된 구간에 있는 수들보다 작거나 같다. 그러면 이 회색 부분은 볼 필요가 없습니다. 이제 문제는 진하게 표시된 보라색 부분입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select12.png)
a[x]가 a[i]보다 크다고 하겠습니다. 이 상황을 #1이라 하겠습니다. 그렇다면 이 a[x]는 언제 뽑힌 걸까요? x번째 사이클에 뽑힌 것입니다. 이 상황으로 돌아가 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select13.png)
먼저, a[x]라는 값이 처음에 x번째 위치에 있지 않았을 때를 생각해 봅시다. 이 경우, 제가 표시한 회색 구간에서 주황색으로 표시한 게 뽑힐 수 있나요? a[x] > a[i] 이므로 그럴 수 없습니다. 최소한 a[x]는 뽑히지 않을 겁니다. 왜? a[x]보다 더 작은 a[i]가 있기 때문입니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select14.png)
a[x]가 기존에 x번째 위치에 있었다고 해도 마찬가지입니다. 회색 구간에 a[i]가 있는데, 이미 a[i] < a[x]입니다. 따라서 x번째 사이클이 끝난 후에 a[x]는 x번째 자리에 있을 수 없습니다. 즉 #1과 같은 상황은 일어날 수 없고, 정렬이 정상적으로 수행됩니다.
stable sort인가?
그러면 선택 정렬은 stable 할까요? 아니라는 것을 손쉽게 알 수 있습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select15.png)
배열 arr에 2, 2, 2, 1 순서대로 있고, 오름차순으로 정렬해야 한다고 해 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select16.png)
회색 구간에서 최소값은 1입니다. 그러면, 노란색으로 칠한 부분하고 1을 바꿀 겁니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select17.png)
바꾼 후에는 위와 같이 됩니다. f라고 표시한 2가 맨 뒤로 갔습니다. 즉, 같은 우선순위를 가지는 원소에 대해, 정렬을 하기 전과 후의 순서가 다릅니다. 따라서 unstable 합니다.
코드
이제, 선택 정렬 코드를 간단히 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select1.png)
먼저, 크기가 10인 arr 배열이 있습니다. change 함수가 있는데요. lo1번째 원소와 lo2번째 원소를 바꾸기 위함입니다. c++을 쓰시는 경우, algorithm 헤더의 swap 함수를 이용하시면 됩니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select2.png)
다음, for loop 부분이 핵심입니다. 사이클을 sz-1회 도는데요. 사이클을 돌 때 마다 어떻게 하나요? i+1번째 원소부터 끝의 원소 중 최소값을 가지는 원소를 찾아요. 이것을 mn이 들고 있어요. 다음에 arr[lo]가 arr[i]보다 작으면 이 둘을 바꿉니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/11/select3.png)
실행 결과는 위와 같습니다.
안녕하세요.
문의드릴 게 있는데 메일 주소 하나 부탁드려도 될까요 ?
메일은 codingdog03@gmail.com 으로 보내주세요.
메일 드렸습니다. 확인 부탁드립니다.