SelectionSort

첫째는 SelectionSort, 선택 정렬이다.

원리

1. 0부터 끝요소까지 반복한다.( current < N )

2. 현재요소( current )와 나머지 요소 중 가장 작은 값을 비교하여 더 작다면 교환이 일어난다.

특징

1. 가장 작은 값을 찾는 과정에서 비교는 여러번 일어나지만 실제로 교환은 한번만 일어 나므로 범위가 작을경우 유리하다.

2. 데이터양이 큰 경우 매번 작은 값을 찾기 때문에 매우 느리다.

연산시간

1. 최선의 경우 비교횟수 : N - 1 ( 정렬이 이미 되어 있는 경우 )

2. 최악의 경우 비교횟수 :N * (N - 1) / 2 ( 역순으로 정렬되어 있는 경우 )

- 처음에는 가장 작은 값을 찾기위해 (N - 1) 번 비교할 것이며 하나씩 정렬 될 때마다 -1 씩 하여 끝에는 1번 비교하게 될 것이다. 

즉, 비교횟수는 [ (N - 1) + (N - 2) + (N - 3) ... 1 ]이다. 

식으로 나타내면   = n(n-1) / 2 이며 O표기법으로는 O(n^2)이 된다.

코드

//SELECTIONSORT
 
void SelectionSort(int* array, int size)
{
    for (int i = 0; i < size; i++)         // i == (0 ~ size)
    {
        for (int j = i; j < size; j++){    // j == (i ~ size)
            if (array[i] > array[j])       // (i) > (j) 이면 교환
            {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }
    }
}
int const MAX = 5;                        // Max 값
int g_arr[MAX] = { 0, };                  // 배열 초기화
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);        // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);       // 역순 배열 생성
    RandomNumber(g_arr, MAX);             // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);              // 배열 출력
    printf("\n");
    clock_t start = clock();              // 시작 시간
    SelectionSort(g_arr, MAX);            // SelectionSort
    clock_t end = clock();                // 끝 시간
 
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);              // 배열 출력
    printf("\nTime : %f\n", ((double)(end - start)) / CLOCKS_PER_SEC);
}

결과

시간

시간은 MAX 값 100,000 을 기준으로 측정하였다.

랜덤 배열 : 31.60
역순 배열 : 19.13
순열 배열 : 13.20

결론

선택정렬은 가장 직관적인 정렬인것 같다. (최소값을 앞에 정렬하는 것이기 때문)

또 10000개 이하 개수에 대해서는 비교하는 것에 비해 교환횟수가 적기 때문에 빠른 속도를 나타낸다.(10000개 기준 0.64초)

하지만 O(n^2)의 알고리즘 답게 요소가 많아질 수록 응답 시간이 길어지는 것이 확실히 보인다.