개요[편집 / 원본 편집]
선택 정렬이란, [math]\displaystyle{ N-1 }[/math]번부터 1번 까지의 자리에 대하여 해당 자리에 넣어야 하는 원소를 선택하는 알고리즘이다. 오름차순으로 정렬한다면, [math]\displaystyle{ N-1 }[/math]번부터 1번 까지의 자리에는 남아있는 수들 중 가장 큰 수를 선택하여 넣어야 한다.
예시[편집 / 원본 편집]
[math]\displaystyle{ N = 8 }[/math]인 다음과 같은 수열을 오름차순으로 정렬한다고 할 때,
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 7 | 2 | 1 | 6 | 5 | 4 | 0 |
7번째 자리에 위치해야 할 숫자는 인덱스 0번부터 7번까지에 있는 숫자들 중 가장 큰 숫자가 된다.
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 7 | 2 | 1 | 6 | 5 | 4 | 0 |
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 0 | 2 | 1 | 6 | 5 | 4 | 7 |
따라서 0번부터 7번 까지의 인덱스를 순회하여 가장 큰 숫자가 있는 인덱스 1번을 알아낸다.
이후, 인덱스 7번에 있는 숫자 0과 1번에 있는 숫자 7을 swap()
함수를 이용하여 교환한다.
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 0 | 2 | 1 | 6 | 5 | 4 | 7 |
6번째 자리에 위치해야 할 숫자는 인덱스 0번 부터 6번 까지 있는 숫자들 중 가장 큰 숫자가 된다.
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 0 | 2 | 1 | 6 | 5 | 4 | 7 |
arr[idx] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|---|
3 | 0 | 2 | 1 | 4 | 5 | 6 | 7 |
따라서 0번부터 6번까지의 인덱스를 순회하여 남아있는 숫자들 중 가장 큰 숫자가 있는 인덱스 4번을 알아낸다.
이후, 인덱스 6번에 있는 숫자 4와 인덱스 4번에 있는 숫자 6의 자리를 swap()
함수로 교환한다.
이와 같은 과정을 N-1
번 반복하여 남아있는 수들 중 가장 큰 수를 각 인덱스로 위치시킨다.
코드[편집 / 원본 편집]
#include <iostream>
using namespace std;
int n = 8;
int arr[8] = {3, 7, 2, 1, 6, 5, 4, 0};
void selectionSort(int st, int en) {
for (int i=n-1; i>0; i--) { //i번째 자리에 위치해야 하는 원소 선택
int maxidx = 0; //남아있는 원소들 중 가장 큰 수가 있는 인덱스
for (int j=1; j<=i; j++) {
if (arr[maxidx] < arr[j]) maxidx = j;
}
swap(arr[i], arr[maxidx]);
}
}
void printarr() {
for (int i=0; i<n; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
int main() {
selectionSort(0, n);
printarr();
return 0;
}
/*output:
0 1 2 3 4 5 6 7 */
시간 복잡도[편집 / 원본 편집]
선택정렬의 시간 복잡도는 외부의 루프를 (N-1)
번 도는 동안, 각 자리에 와야하는 최댓값을 구하기 위하여 [math]\displaystyle{ N-1, N-2, N-3, ... , 1 }[/math]번의 비교연산을 수행한다.
따라서, [math]\displaystyle{ T(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2 }[/math]
시간복잡도는 [math]\displaystyle{ O(n) = n^2 }[/math] 이다.
안정성과 제자리성[편집 / 원본 편집]
선택정렬 알고리즘으로 정렬을 수행하는 경우 동일한 값을 가지는 원소들의 본래 순서가 보장되지 않는다. 따라서 선택정렬은 불안정정렬(Unstable sort)이다. 또한, 기존 배열 이외의 추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort)이다.