이번 시간에는 기본 정렬의 마지막 선택 정렬입니다.
선택 정렬은 버블, 삽입 정렬과 다르게 불안정 정렬입니다.
이 부분에 대해서 글 마지막 부분에 추가적으로 설명해 드리니 집중해서 봐주세요!
선택 정렬(Selection sort) - 불안정 정렬(Unstable sort)
선택 정렬은 매 회전마다 가장 적합하다고 판단되는 값을 선택해 나가는 방법이다.
만약 오름차순으로 정렬한다면, 매 회전마다 가장 작은 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.
(맨 앞 자리는 i번째 회전 때 배열의 i번째 요소입니다.)
반대로 내림차순으로 정렬한다면, 매 회전마다 가장 큰 값을 선택해 맨 앞 자리 수와 교환하는 것 입니다.
여기서 선택을 한다는 의미는 해당 인덱스를 기억해 맨 앞자리 원소와 교환한다는 의미입니다.
조금 더 자세하게 그림으로 보여드리겠습니다.
1회전 :
배열의 처음부터 끝까지 탐색하여 최적 값(1)의 Index를 찾습니다.
그리고 선택 위치 Index의 값(7)과 최적 값(1)을 교환합니다.
2회전 :
배열의 두 번째 부터 끝까지 탐색하여 최적 값(2)의 Index를 찾습니다.
그리고 선택 위치 Index의 값(3)과 최적 값(2)을 교환합니다.
3회전 :
배열의 세 번째 부터 끝까지 탐색하여 최적 값(3)의 Index를 찾습니다.
그리고 선택 위치 Index의 값(3)과 최적 값(3)을 교환합니다.
4회전 :
배열의 네 번째 부터 끝까지 탐색하여 최적 값(5)의 Index를 찾습니다.
그리고 선택 위치 Index의 값(5)과 최적 값(5)을 교환합니다.
데이터가 하나 남았으므로 더 이상 비교할 데이터가 없으니 끝냅니다.
소스 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <iostream> using namespace std; //교환 void swap(int * num1, int * num2){ int temp; temp = *num1; *num1 = *num2; *num2 = temp; } int main() { int a[5] = {7,3,2,1,5}; int min; //선택 정렬 for(int i = 0; i<4; i++){ min = i; for(int j = i+1; j<5; j++){ if(a[j] < a[min]) min = j; } swap(&a[min],&a[i]); } //출력 for(int i = 0; i<5 ; i++) cout << a[i] << " "; return 0; } | cs |
Line 24 : 최적 값의 위치와 선택 위치의 값을 교환합니다.
시간 복잡도
선택 정렬은 기존 데이터의 구성에 따라 비교 횟수가 변하지 않고,
모든 비교를 진행하기 때문에 n-1 부터 1 까지 등차수열의 합입니다.
따라서 시간복잡도는 이 됩니다.
왜 불안정정렬인가?
가장 간단하게 선택 정렬시에 불안정 정렬이 되는 예를 보여드리겠습니다.
다음과 같은 카드들이 있습니다.
이 카드들에서 숫자5를 가진 카드들만 본다면 다이아몬드5 - 스페이스5의 순서를 확인 할 수 있습니다.
만약 이 상황에서 카드의 숫자를 기준으로 오름차순으로 정렬하면 1회전때 다음과 같은 교환이 일어납니다.
그리고 나서 결과를 살펴보면 아래와 같이 변합니다.
결국 1회전 이후 완전히 정렬되었으므로 2, 3, 4 회전때는 교환이 일어나지 않습니다.
최종 정렬 결과를 살펴보면 기존의 다이아몬드5 - 스페이스5 순서가 뒤바뀐 모습을 볼 수 있습니다.
이는 앞서 설명했던 불안정 정렬의 기존 순서를 보존하지 않는 특성입니다.
따라서 선택 정렬은 불안정 정렬입니다.
만약 어떤 데이터를 정렬할 때, 위와 같은 결과를 원하시지 않으면 안정 정렬 알고리즘을 선택하는 게 옳습니다.
지금까지 버블, 삽입 정렬에 이어 선택 정렬을 살펴봤습니다.
다음 글 부터는 본격적으로 고급 알고리즘에 대해서 포스팅 해보도록 하겠습니다.
감사합니다!
'공부 > 알고리즘' 카테고리의 다른 글
[알고리즘] - 합병 정렬(Merge sort) #7 (2) | 2019.02.06 |
---|---|
[알고리즘] - 퀵 정렬(Quick sort) #6 (0) | 2019.01.31 |
[알고리즘] - 삽입 정렬(Insertion sort) #4 (3) | 2019.01.15 |
[알고리즘] - 버블 정렬(Bubble Sort) #3 (1) | 2019.01.10 |
[알고리즘] - 안정 정렬(Stable Sort)과 불안정 정렬(Unstable Sort) #2 (5) | 2019.01.09 |