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

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

 

배열 a에서

아직 정렬하지 않은 부분에서 가장 작은 키의 값 a[min]을 선택한다.

a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

 

이 과정을 n - 1회 반복한다.

#define swap(type, x, y) do { type t = x; x = y; y = t; } while(0)

// 단순 선택 정렬
void selection(int a[], int n) {
    int i, j;
    
    for(i = 0; i < n - 1; i++) {
        int min = i;
        for(j = i + 1; j < n; j++) {
            if(a[j] < a[min])
                min = j;
        }
        swap(int, a[i], a[min]); // 이렇게 하면 min == i 일 경우에도 실행은 되나 결과는 같음 (오히려 두 값이 다를 때에만 적용하게 비교하는 구문을 삽입하는게 전체 프로그램의 효율을 떨어뜨릴 수도 있음)
    }
}

 

서로 떨어져 있는 요소를 교환하기 때문에 알고리즘이 안정적이지 않다. ( 값이 같은 요소가 중복해 있을 때 정렬 전/후의 순서가 뒤바뀔 수 있다)

 

시간복잡도 : O(n^2)