삽입정렬 (Insertion Sorting)

삽입 정렬은 오름차순 기준으로, 정렬이 완료된 기존의 카드 사이에 올바른 자리를 찾아 삽입하는 정렬이다.

1. 정렬되어 있지 않은 리스트의 첫 번째 숫자를 선택

2. 자신을 기준으로 인덱스를 감소시키며(뒤에 부터) 하나 씩 비교해 가며 자신보다 작은 숫자를 찾는다.

3. 자신보다 크다면 그 숫자를 뒤로 한 칸 미룬다.

4. 자신보다 작다면 연산을 멈춘다.

5. 위 과정을 정렬되어 있지 않은 리스트의 마지막 요소까지 반복

주의할 점은, index를 앞에서 부터 비교하는 것이 아니라 뒤에서 부터 비교한다. 즉, (자신의 인덱스-1)번부터 0번까지비교하여 인덱스가 점점 감소한다. 그리고 첫 회전에서 시작은 0번이 아니라 1번부터 시작한다.

예를 들어 요소의 갯수가 5개이고

3 2 6 1 5  라는 배열이 있다면

1스캔 - 2 3 6 1 5

2스캔 - 2 3 6 1 5

3스캔 - 1 2 3 6 5

4스캔 - 1 2 3 5 6

위와 같은 절차가 행해진다.

삽입정렬의 코드는 다음과 같다.

void insertion_sort(int list[], int n) {
    for (int i = 1; i < n; i++) {
        int key = list[i];
        int j;
        for (j = i - 1; j >= 0 && list[j] > key; j--)
            list[j + 1] = list[j]; // 레코드의 오른쪽으로 이동
        list[j + 1] = key;
    }
}

전체 프로그램

정렬하기 전의 배열 상태와 각 회전수에 정렬된 배열 상태를 출력한다.

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

#define MAX_SIZE 10

void insertion_sort(int list[], int n) {
    for (int i = 1; i < n; i++) {
        int key = list[i];
        int j;
        for (j = i - 1; j >= 0 && list[j] > key; j--)
            list[j + 1] = list[j]; // 레코드의 오른쪽으로 이동
        list[j + 1] = key;
    
        printf("%d회 정렬 결과 : ", i);
        for (int k = 0; k < n; k++)
            printf("%d ", list[k]);
        printf("\n");
    }
}

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

    printf("<삽입정렬>\n정렬 이전 배열 : ");
    for (int i = 0; i < n; i++) {// 난수 생성 및 출력
        list[i] = rand() % n; // 난수 발생범위 0 ~ n
        printf("%d ", list[i]);
    }
    printf("\n");

    insertion_sort(list, n); // 삽입 정렬 호출

    printf("최종 정렬 결과 : ");
    for (int i = 0; i < n; i++) // 정렬 결과 출력
        printf("%d ", list[i]);
    printf("\n");
    system("pause");
}

 

<성능평가>

4만개의 크기를 주고 시간을 재는 코드는 다음과 같다.

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

#define MAX_SIZE 40000

void insertion_sort(int list[], int n) {

    clock_t start = clock(); // 시간재기 시작
    for (int i = 1; i < n; i++) {
        int key = list[i];
        int j;
        for (j = i - 1; j >= 0 && list[j] > key; j--)
            list[j + 1] = list[j]; // 레코드의 오른쪽으로 이동
        list[j + 1] = key;
    }
    clock_t end = clock(); // 시간재기 끝
    
    double diff = (double)(end - start) / 1000;
    printf("삽입정렬\n크기 : 40000개\n%.4lf초", diff);

}

void main() {
    int list[MAX_SIZE];
    int n = MAX_SIZE;
    
    for (int i = 0; i < n; i++) {// 난수 생성
        list[i] = rand() % n;
    }
    
    insertion_sort(list, n);
    
    printf("\n");
    system("pause");
}

 

삽입정렬의 복잡도는 입력 자료의 구성에 따라 달라진다.

입력 자료가 이미 정렬되어 있는 경우 가장 빠르다.

이 경우 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 이동 없이 1번의 비교만 이루어 지므로 총 비교 횟수는 n-1번이 된다.

모든 배열이 정렬될 떄 까지 이를 반복하는데, n번 반복하게된다.

따라서 알고리즘의 시간 복잡도는 O(n^2)이다.

최악의 복잡도는 입력 자료가 역순일 경우로서 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다.

최악의 경우는 외부 루프 안의 각 반복마다 i번의 비교가 수행되므로 총 비교 횟수는 다음과 같다.

 

 

총 이동 횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로

 

 

삽입 정렬은 비교적 많은 레코드들의 이동을 포함하며, 결과적으로는 레코드 수가 많은 경우 적합하지 않다.

하지만, 안정한 정렬 방법으로서 레코드의 수가 적을 경우, 알고리즘이 간단하므로 다른 복잡한 정렬방법 보다 유리할 수 있다.

또한 대부분의 레코드가 이미 정렬이 되어있는 경우 매우 효과적이다.