[알고리즘] 선택 정렬 (Selection Sort)

알고리즘

선택 정렬(Selection Sort)의 알고리즘은 다음과 같습니다.

• 전체를 탐색해 최솟값을 찾아 첫 번째 원소로 저장
• 첫 번째 원소를 제외하고 나머지를 탐색해 최솟값을 두 번째 원소로 저장
• 전체를 탐색할 때까지 이를 반복

예를 들어 다음 배열을 정렬해 보겠습니다.

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

1)   전체를 탐색해 최솟값인 "1"을 찾아내고, 제일 앞의 원소와 바꿔 줍니다

[4 , 6 , 8 , 1 , 3 , 5 , 7 , 2 , 10 , 9]

[1 , 6 , 8 , 4 , 3 , 5 , 7 , 2 , 10 , 9]

 

2)   1을 제외한 나머지를 탐색해 최솟값인 "2"을 찾아내고 1을 제외하고 제일 앞의 원소와 바꿔 줍니다.

[1 , 6 , 8 , 4 , 3 , 5 , 7 , 2 , 10 , 9]

[1 , 2 , 8 , 4 , 3 , 5 , 7 , 6 , 10 , 9]

 

3)   1,2를 제외한 나머지를 탐색해 최솟값인 "3"을 찾아내고, 1,2를 제외하고 제일 앞의 원소와 바꿔 줍니다.

[1 , 2 , 8 , 4 , 3 , 5 , 7 , 6 , 10 , 9]

[1 , 2 , 3 , 4 , 8 , 5 , 7 , 6 , 10 , 9]

 

이렇게 전체 배열이 정렬될 때까지 반복합니다.

[1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10]

---

시간 복잡도

선택 정렬의 시간 복잡도는 O(N^2)입니다.

 

이는 엄청 비효율적인 시간 복잡도죠.

 

위의 예제를 예로 들어 왜 선택 정렬의 시간 복잡도가 O(N^2)인지에 대해 설명하겠습니다.

 

첫 번째 단계에서 최솟값을 찾기 위해 첫 번째 수부터 배열의 길이인 10번째 수까지 탐색하죠.

이때의 탐색 횟수는 10번입니다.

 

두 번째 단계 예서 1을 제외하고 최솟값을 찾기 위해 두 번째 수부터 열 번째 수까지 탐색합니다.

이때의 탐색 횟수는 9번입니다.

 

세 번째 단계에서 1,2를 제외하고 최솟값을 찾기 위해 세 번째 수부터 열 번째 수까지 탐색합니다.

이때의 탐색 횟수는 8번입니다.

 

...

 

마지막 단계에서 1,2,3,4,6,7,8,9를 제외하고 최솟값을 찾기 위해 마지막 수를 탐색합니다

이때의 탐색 횟수는 1번입니다.

 

10개의 숫자를 정렬하기 위해 탐색한 숫자는 10번+9번+8번+ ... + 1번입니다.

 

1부터 N까지의 합 공식을 적용하면 다음과 같습니다.

 

N x (N+1) / 2

 

즉, 선택 정렬의 시간 복잡도는 O(N^2)입니다.

---

소스코드

위의 내용을 바탕으로 C++로 소스코드를 작성해 보겠습니다.

 

#include <iostream>
using namespace std;

int main(void) {
    //정렬할 배열
    int array[10] = { 4,6,8,1,3,5,7,2,10,9 };
    //최솟값 구할때 비교할 숫자 
    int min;
    //최솟값 index
    int index = 0;
    //swap할때 사용할 변수
    int temp;

    //정렬할 배열 크기만큼 반복
    for (int i = 0; i < 10; i++) {
        //최솟값 구할때 숫자 여유롭게 크게 부여
        min = 9999;
        //정렬된 부분 제외하고 나머지 부분에서 최솟값 탐색
        //j는 i부터 시작하는 것 참고
        for (int j = i; j < 10; j++) {
            //최솟값, 최솟값의 index 저장
            if (min > array[j]) {
                min = array[j];
                index = j;
            }
        }
        //최솟값과 제일 앞의 값 Swap
        temp = array[i];
        array[i] = array[index];
        array[index] = temp;

    }

    //정렬된 배열 출력
    for (int i = 0; i < 10; i++) {
        cout << array[i] << " ";
    }

    return 0;
}

 

위 코드를 실행시켜 보면 다음과 같이 정렬된 배열을 확인할 수 있습니다.