이번 시간에는 기본 정렬의 마지막 선택 정렬입니다.


선택 정렬은 버블, 삽입 정렬과 다르게 불안정 정렬입니다.


이 부분에 대해서 글 마지막 부분에 추가적으로 설명해 드리니 집중해서 봐주세요!




선택 정렬(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

배열 a : 정렬하고자 하는 데이터 입니다.

min : 가장 적합한 값의 index 입니다.

Line 6-11 : Swap 함수의 정의입니다.

Line 19 : 선택 위치의 값을 제일 최적 값이라고 생각하고 시작합니다.

Line 20-23 : 선택 위치+1 부터 배열의 끝까지 탐색해 나가며 최적 값의 index를 갱신합니다. 

Line 24 : 최적 값의 위치와 선택 위치의 값을 교환합니다.




시간 복잡도


선택 정렬은 기존 데이터의 구성에 따라 비교 횟수가 변하지 않고, 


모든 비교를 진행하기 때문에 n-1 부터 1 까지 등차수열의 합입니다.


따라서 시간복잡도는 이 됩니다.




왜 불안정정렬인가?


가장 간단하게 선택 정렬시에 불안정 정렬이 되는 예를 보여드리겠습니다.


다음과 같은 카드들이 있습니다.




이 카드들에서 숫자5를 가진 카드들만 본다면 다이아몬드5 - 스페이스5의 순서를 확인 할 수 있습니다.


만약 이 상황에서 카드의 숫자를 기준으로 오름차순으로 정렬하면 1회전때 다음과 같은 교환이 일어납니다.





그리고 나서 결과를 살펴보면 아래와 같이 변합니다.



결국 1회전 이후 완전히 정렬되었으므로 2, 3, 4 회전때는 교환이 일어나지 않습니다.


최종 정렬 결과를 살펴보면 기존의 다이아몬드5 - 스페이스5 순서가 뒤바뀐 모습을 볼 수 있습니다.


이는 앞서 설명했던 불안정 정렬의 기존 순서를 보존하지 않는 특성입니다.


따라서 선택 정렬은 불안정 정렬입니다.


만약 어떤 데이터를 정렬할 때, 위와 같은 결과를 원하시지 않으면 안정 정렬 알고리즘을 선택하는 게 옳습니다.



지금까지 버블, 삽입 정렬에 이어 선택 정렬을 살펴봤습니다. 


다음 글 부터는 본격적으로 고급 알고리즘에 대해서 포스팅 해보도록 하겠습니다.


감사합니다!







저번 포스팅에서 언급했듯이 정렬에 대해서 알아보도록 하겠습니다.


우선 정렬 알고리즘을 배우기 전에 정렬의 안정적 특성에 대해서 알아야 할 필요가 있습니다.


이 특성을 모르고 정렬 알고리즘을 선택한다면, 우리가 원하는 결과를 얻지 못할 수 있기 때문입니다.




정렬의 안정적 특성이란?


정렬의 안정적 특성이란 "정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지되느냐" 입니다.


이러한 정렬의 안정적 특성에 따라서 정렬 알고리즘은 안정 정렬과 불안정 정렬로 구분 할 수 있습니다.


예를 들어, 아래와 같은 포커 카드에 대해서 번호를 키값으로 하여 오름차순으로 정렬하고자 합니다


이때, 우리는 약간 이상한 성향으로 인해(?) 같은 숫자카드의 무늬 순서를 유지시키고자 합니다.


즉, 아래 그림의 경우 정렬 후에도 하트4 뒤쪽에 스페이스4가 위치하게 하고 싶다는 의미입니다.


"당연히 유지되는게 정상 아니야?" 라고 생각 하실 수 있지만, 정렬 알고리즘에 따라서 정렬 후에 이 순서가 바뀔 수도 있습니다.



안정 정렬(Stable Sort) 


안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지되며, 결과는 다음과 같습니다.


정렬된 결과에서 하트4와 스페이스4의 순서가 그대로 유지되고 있음을 확인 할 수 있습니다.



불안정 정렬(Unstable Sort)


불안정 정렬의 경우에는 정렬 후에도 원래의 순서가 유지된다는 보장을 할 수 없으며, 결과는 다음과 같을 수 있습니다.


안정 정렬의 결과와는 달리 스페이스4와 하트4의 순서가 바뀐 모습을 확인 할 수 있습니다.

 




앞으로 배울 정렬 알고리즘에는 안정 정렬 알고리즘도 있고, 불안정 정렬 알고리즘도 있습니다.


따라서 이를 구분해서 학습을 해야 합니다. 너무 걱정하지는 마세요! 정렬 알고리즘을 설명할 때 같이 하도록 하겠습니다.


이번 포스팅은 여기까지며 다음 글부터 본격적으로 정렬 알고리즘에 대해서 알아보도록 하겠습니다!





+ Recent posts