C언어 | 단순 삽입 정렬 (straight insertion sort) | 기본 정렬

단순 삽입 정렬은 (straight insertion sort) 말 그대로 선택한 요소를 압쪽으로 삽입하는 작업을 반복하여 정렬한다.

 

단순 선택 정렬과 비슷해 보이지만 삽입정렬은 왼쪽으로 삽입하고 나머지를 오른쪽으로 미는 방식이고 단순 선택 정렬은 값이 가장 작은 요소를 앞으로 끌고오는 방식이다.

 

둘다 시간 복잡도는 O(n^2) 이다. 단순정렬 3종 세트(버블, 선택, 삽입)의 시간복잡도는 모두 O(n^2) 이다. 이 세개는 세트로 배워두는게 좋다. n2 는 굉장히 큰 숫자인데 n이 작업의 단위를 말하는 것이면 100개의 요소가 있는 배열은 정렬한번에 1만번 작업이 실시되고, 1000개의 요소를 정렬하려면 1000,000 회(100만) 작업이 필요하다는 것이다. 실로 놀라운 숫자라고 할 수 있다. 컴퓨터의 세계에서 1,000개의 데이터는 작은 숫자다. 반면 1000개의 데이터를 위해 사용하는 100만회나 되는 작업은 적지 않다. 그래서 본능적으로 거부감이 들게 하는 정렬방식이다.

 

그러나 단순정렬을 배우는 장점이 있다. 더 좋은 알고리즘이 무엇인지 사람들이 자각하게 해준다. 또 단순정렬을 응용해서 더 나은 알고리즘을 개발할 수 있는 기대를 한다. 왜 이런 재미없는 과정을 거쳐야 하는지 생각해볼 필요가 있다. 대부분 입문 교재에서 다루는 내용은 비슷하니 익숙해지면 좀 더 나은 방법을 찾을 수 있을 것이다.

 

 

* 삽입 정렬을 다음의 배열로 알아보자.

 

 

array	i	j	key	j >= 0	arr[j]	arr[j] > key
*[1] 7 5 2 3 4 6 1	1	0 = (i - 1)	5	true	7 = arr[0]	true (7 > 5)
*[1] 5 7 2 3 4 6 1	1	-1	5	false
*[2] 5 7 2 3 4 6 1	2	1 = ( i - 1)	2	true	7 = arr[1]	true (7 > 2)
*[2] 5 7 7 3 4 6 1	2	0	2	true	5 = arr[0]	true (5> 2)
*[2] 5 5 7 3 4 6 1	2	-1	2	false
*[3] 2 5 7 3 4 6 1	3	2 (i - 1)	3	true	7 arr[2]	true (7 > 3)
...

*[1] 에서 arr[j+1] = arr[j]

-> arr[1] = arr[0] = 7 로 변경 후 j-- 하면 j는 -1 이 되므로 첫번째 while 루프 종료. key = 5가 arr[-1+1] = arr[0] 에 입력된다.

 

*[2] 에서 arr[2] = arr[1] = 7 로 변경. j-- 로 j 는 0 이 된다. while 루프를 한번 더 간다.

 

루프를 돌면 arr[1] = arr[0] = 5. j-- 로 -1가 되므로 두번째 루프 종료. key 2가 arr[-1+1] = arr[0] 에 입력된다.

 

이렇게 진행을 하다가 for문은 i가 6이 되고 arr[6] 마지막 요소를 키값으로 arr[6-1] 요소와  비교하는 것으로 루프가 끝난다.

 

j = i - 1 이므로 j + 1 = i 다. arr[j+1]은 곧 arr[i] 와 같다.

 

array 가 변하는 모습을 보면 오른쪽에서 숫자 하나를 꺼내서 밀고 왼쪽에 삽입하는 과정을 알 수 있다. 하나씩 밀기 때문에 key 변수 하나의 공간으로도 정렬이 가능하다.

 

막상 타이핑을 치며 따라해 보면 헷갈릴 수 있으니까 연필로 공책에 쓰면서 해보면 더 좋다.

 

또 이것만 삽입정렬이 가능한게 아니라 다른 소스 코드로도 가능하니 자기가 이해하기 쉬운 코드를 분석하면 좋다. 결국 로직은 갖아진다. 문법상 약간 차이가 있다.

 

*전체 소스코드

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

#define Line printf("\n-------------------------------------------------\n");

void swap(int *x, int *y);
int getRandomInt(int from, int to);
int* getArray(int count);
void showArray(int arr[], int count);
void insertionSort(int arr[], int n);


int main(int argc, char const *argv[])
{   
    srand(time(NULL));
    /*----- 기본배열 삽입정렬 ----*/

    int array[] = {7, 5, 2, 3, 4, 6, 1};

    Line;
    showArray(array, 6);
    insertionSort(array, 6);
    showArray(array, 6);


    /* ---- 랜덤생성 후 삽입정렬 ---*/

    int count = 5;
    int* array1 = getArray(count);

    Line;

    showArray(array1, count);
    insertionSort(array1, count);
    showArray(array1, count);

    return 0;
}

void insertionSort(int arr[], int n){
    int i, j, key;
    for (i = 1; i < n; i++)
    {
        key = arr[i];
        j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key; 
    }
}

void showArray(int arr[], int count)
{   
    printf("[Show Array]\n");
    printf("[");
    for (int i = 0; i < count; i++)
    {
        printf("%d, ", arr[i]);
    }
    printf("]\n");
    
}

void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int getRandomInt(int from, int to)
{
    int random = rand() % (to-from+1) + from;
    return random;
}

int* getArray(int count)
{
    int *array = calloc(count, sizeof(int));
    for (int i = 0; i < count; i++)
    {
        array[i] = getRandomInt(1,100);   
    }
    return array;
}