Sort/정렬 - Selection Sort/선택 정렬

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.

예를들어 배열안의 원소가 { 3, 2, 5, 4, 1 }일 때 원소가 교환이 일어난 것만 표현할 경우

{ 1, 2, 5, 4, 3 } -> { 1, 2, 3, 4, 5 }순으로 정렬이 완료된다.

알고리즘

1. 아직 정렬하지 않은 부분에서 가장 작은 값의 인덱스를 선택한다.

2. 가장 작은값의 인덱스의 요소와 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

이걸 n - 1회 반복해주면 된다.

 

코드

// 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘
void Selection_Sort(int arr[], int size){
    for(int i = 0; i < size - 1; i++){
        int min = i; // min은 a[i] ~ a[size - 1]에서 가장 작은 값을 가지는 인덱스
        for(int j = i + 1; j < size; j++){
            if(arr[j] < arr[min]){ // arr[min]보다 작은 요소가 있다면
                min = j; // min값을 갱신
            }
        }
        arr[i] ^= arr[min] ^= arr[i] ^= arr[min]; // arr[i]와 arr[min]의 값을 교환
    }
}

선택 정렬의 시간 복잡도는 O(n^2)이며 버블 소트와 마찬가지로 오래걸린다.

하지만 선택 정렬은 버블 소트와는 다르게 불안정 정렬이다.