[알고리즘] - 선택 정렬(Selection sort) #5

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

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

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

선택 정렬(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)을 교환합니다.

데이터가 하나 남았으므로 더 이상 비교할 데이터가 없으니 끝냅니다.

소스 코드

#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;
}
 

배열 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 순서가 뒤바뀐 모습을 볼 수 있습니다.

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

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

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

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

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

감사합니다!