선택 정렬(Selection Sort)

선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘입니다. 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈 ㅏ리에 가져다 놓습니다.

#include <stdio.h>
 
void SelSort(int arr[], int n) {
    int i, j;
    int maxIdx;
    int temp;
 
    for (i = 0; i < n - 1; i++) {
        maxIdx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[maxIdx])
                maxIdx = j;
        }
        temp = arr[i];
        arr[i] = arr[maxIdx];
        arr[maxIdx] = temp;
    }
}
 
int main(void) {
    int arr[4] = { 3,4,2,1 };
    int i;
 
    SelSort(arr, sizeof(arr) / sizeof(int));
    for (i = 0; i < 4; i++)
        printf("%d ", arr[i]);
    printf("\n");
 
    return 0;
}

바깥 for문의 i가 0일 때 안쪽 for문의 j는 1부터 n-1까지 증가하여 선택 정렬의 비교 연산은 n-1회 진행됩니다. 그리고 바깥쪽 for문의 i가 1일 때는 안쪽 for문의 j가 2부터 n-1까지 증가하여 선택 정렬의 비교연산은 n-2회 실행됩니다. 비교 연산의 횟수는 (n-1) + (n-2) + ... + 2 + 1 로 버블 정렬과 동일 합니닫. 따라서 선택 정렬의 빅오는 O(n^2) 입니다. 그렇다면 데이터의 이동 횟수도 버블 정렬과 차이가 없을까? 아니다. 데이터의 교환을 위한 대입 연산이 존재하는 위치가 다르다. 버블 정렬의 경우에는 안쪽 for문에 있고, 선택 정렬의 경우에는 바깥쪽 for문에 속해 있습니다. 따라서 선택 저열의 경우 n-1회의 교환이 이루어지므로 데이터의 이동횟수는 이의 3배인 3(n-1)이 됩니다. 즉, O(n).  최악의 경우만 놓고보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한 번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지 않는다는 사실을 감안하면, 둘의 우열을 가리는 것은 무의미합니다.