3. 삽입 정렬(Insertion Sort)

Goal

---

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

 

Insertion Sort란?

---

손 안의 카드를 정렬하듯이, 2번째 원소부터 시작하여 마지막 원소까지, 앞의 원소들과 비교 후 조건에 부합하지 않을 때 까지 교환하는 방식이다. 대략적인 과정은 아래를 따른다.

1. 2번째 위치의 원소를 임시공간에 집어넣는다.
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) {
    for(int i=1; i<n; i++){
        int temp = list[i];
        int prev = i - 1;

        while( (prev >= 0) && (list[prev] > temp) ) {
            list[prev + 1] = list[prev];
            prev--;
        }
        list[prev + 1] = 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;
}

 

시간복잡도

---

삽입 정렬은 선택 정렬, 버블 정렬과 마찬가지로 최악의 경우 (n-1) + (n-2) + (n-3) + .... + 2 + 1 => n(n-1)/2, 즉 O(n^2)이다. 이는 평균적인 경우에도 마찬가지를 보여준다.

 

대신, 어느정도 정렬이 되어있는 데이터라면 대부분의 데이터가 한번씩만 비교할 것이다. 비교 할 시 이미 교환 조건을 충족하지 못해 교환이 끝나기 때문이다. 때문에 최선의 경우라면 O(n)의 시간복잡도를 가질 것이다. 이러한 특징은 이미 정렬이 되어있는 배열에 적은 갯수의 자료를 추가/제거 하는 경우에 최고의 정렬 알고리즘이 된다. 공간도 적게 쓰고, 비교를 위한 메모리 공간또한 적게 쓰기 때문이다.

 

공간복잡도

---

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

 

장점

---

• 매우 간단하고, 직관적이다.
• 추가적인 저장 공간을 요구하지 않으므로, 메모리가 극도로 제한된 환경에서 강력한 이점이 있다.
• 데이터 대부분이 정렬이 되어있다면, 매우 효율적일 수 있다.
• 안정정렬이다.
• 같은 Brute Force 알고리즘 중에서 상대적으로 가장 빠르다.

 

단점

---

• 평균/최악 시간복잡도가 매우 비효율적이다.
• 배열이 길이가 길어지면 질수록 비효율적이다.