2. 선택 정렬(Selection Sort)

Goal

---

• Selection Sort란?
• Selection Sort 구현
• Selection Sort 시간복잡도, 공간복잡도 계산

 

Selection Sort란?

---

순서에 맞게 자리를 정하고, 조건에 맞는 원소를 선택 후 교환하며 정렬하는 알고리즘. 대략적인 과정은 아래를 따른다.

1. 교환할 자리를 정하고, 배열 중 최소값을 찾는다.
2. 선택한 자리와 최소값을 교환한다.
3. 선택했던 자리를 제외하고 나머지 배열을 위 방법으로 진행한다.

 

Selection Sort 구현

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_SIZE 10000

int mknum() {
    int random = (rand() % 100) + 1;

    return random;
}

void selection_sort(int list[], int n) {
    int targetMin, temp;

    for(int i=0; i<n-1; i++){
        targetMin = i;
        for(int j=i+1; j<n; j++) {
            if(list[j] < list[targetMin]) {
                targetMin = j;
            }
        }

        //swap target <-> arr[i]
        temp = list[targetMin];
        list[targetMin] = list[i];
        list[i] = temp;
    }
}

int main() {
    int i;
    int n = MAX_SIZE;
    int list[n];

    printf("Unsorted list :");
    for(i=0; i<n; i++) { //make random list
        list[i] = mknum();
        printf(" %d", list[i]);
    }
    printf("\n");

    //timer
    clock_t start, end;

    start = clock();

    selection_sort(list, n);

    end = clock();

    printf("Sorted list :");
    for(i=0; i<n; i++) { //print sorted output
        printf(" %d", list[i]);
    }
    printf("\n");

    //run-time result
    printf("Run time : %f\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

 

시간복잡도

---

선택 정렬은 버블 정렬과 마찬가지로 1회차에는 n-1번 계산하고, 2회차에는 n-2번, 마지막에는 1번 계산이 이루어진다. 때문에 시간복잡도는 (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2, 즉 O(n^2)이다. 이는 최악, 최선의 경우에도 마찬가지로 적용된다.

 

공간복잡도

---

주어진 배열에서 교환이 이루어지므로, 추가적인 공간이 필요없다. 때문에 O(n)이다.

 

장점

---

• 매우 간단하고, 직관적이다.
• 추가적인 저장 공간을 요구하지 않으므로, 메모리가 극도로 제한된 환경에서 강력한 이점이 있다.

 

단점

---

• 시간복잡도가 매우 비효율적이다.
• 불안정 정렬이다.