Selection Sort(선택 정렬)

랜덤으로 정렬된 데이터가 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은데이터와 바꾸고, 그 다음 작은데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복해서 진행하는 정렬방법을 선택 정렬이라고 합니다.

Step 1)

초기 단계는 모든 데이터가 정렬되어 있지 않으므로, 전체 중에서 가장 작은 데이터를 선택하기 때문에 '0'을 선택해 맨 앞에 있는 '7'과 바꿉니다.

Step 2)

이제 정렬된 첫 번째는 제외하고 이후 데이터 중에서 가장 작은 데이터인 '1'을 선택해서 처리되지 않은 데이터 중 가장 앞에 있는 '5'와 바꿉니다. 

Step 3)

이번에도 마찬가지로 가장 데이터인 '2'와 처리되지 않은 데이터 중 가장 앞에 있는 데이터 '9'와 바꿉니다.

 

이처럼 선택 정렬은 가장 작은 데이터를 앞으로 보내는 과정을 N - 1번 반복하면 정렬이 완료되는 것을 알 수 있습니다.

#include <stdio.h>
 
#define MAX_LEN 10
 
void Swap(int *ap_value1, int *ap_value2)
{
    int temp = *ap_value1;
    *ap_value1 = *ap_value2;
    *ap_value2 = temp;
}
 
// 선택 정렬
int main(void) {
    int arr[MAX_LEN] = { 7, 5, 9, 0, 3, 1, 6, 2, 4, 8 };
 
    for (int i = 0; i < MAX_LEN; i++) {
        int min_index = i; // 가장 작은 원소의 인덱스 
        for (int j = i + 1; j < MAX_LEN; j++) {
            if (arr[min_index] > arr[j]) {
                min_index = j;
            }
        }
        Swap(&arr[i], &arr[min_index]); // 스와프
    }
 
    for (int i = 0; i < MAX_LEN; i++)
        printf("%d ", arr[i]);
}

 

시간 복잡도

시간복잡도는 O(N^2)이고 다른 알고리즘과 비교했을 때 매우 비효율적이지만, 특정한 리스트에서 가장 작은 데이터를 찾는 일이 코딩테스트에서 자주 사용되므로 잘 이해하고 있어야한다.