알고리즘 삽입 정렬(Insertion Sort) C언어

▶삽입 정렬

버블 정렬보다 조금 더 나은 정렬.

배열의 앞부분부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아서 삽입한다.

순회한 원소들의 부분 배열은 정렬 상태를 유지함.

평균 성능 시간 복잡도 : O(n^2)

최악 성능 시간 복잡도 : O(n^2)

최선 성능 시간 복잡도 : O(n)

 

▶소스코드

void InsertionSort(int arr[], int size)
{
    int i, j, temp;
    for (i = 1; i < size; i++)
    {
        temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

위 소스는 오름차순 정렬이다.

 

▶해석

자신보다 앞에 있는 원소와 비교해야하기 때문에 i = 1부터 시작한다.

for (i = 1; i < size; i++)

 

temp 변수는 나중에 삽입될 arr[i] 값을 저장하여 arr [i] 값이 바뀌어도 temp은 남아있을 수 있다.

temp = arr[i];

 

초기값을 j = i 로 하여 0이 될 때까지 j-- 해주고 arr [i]의 바로 전 원소 arr [i-1]부터 비교를 시작하기 위해

arr[j-1] > temp을 하였다. i가 증가하면서 arr [0] ~ arr [i-1] 은 정렬된 채로 따라온다. 그러므로 temp이 arr [j-1] 보다 크다면 현재 자리가 temp 이 들어가야 할 자리가 되는 것이기에 반복문을 멈춰야 한다.

for (j = i; j > 0 && arr[j - 1] > temp; j--)

 

arr [j-1] > temp 식이 성립되므로 arr[j-1]은 한칸 밀려나 arr[j]에 들어간다. 이미 앞에서부터 정렬된 상태로 쭉 가기 때문에 뒤로 밀려나는 것이 가능한 것이다.

arr[j] = arr[j - 1];

 

arr[j-1] > temp 식이 성립되지 않으므로 반복문을 빠져나온다. arr [j-1]이 temp보다 작다는 것이 결정되었으니 temp의 자리는 arr [j-1]보다 한 칸 앞인 arr [j]가 되는 것이다.

arr[j] = temp;

 

▶예시

#include <stdio.h>

void InsertionSort(int arr[], int size)
{
    int i, j, temp;
    for (i = 1; i < size; i++)
    {
        temp = arr[i];
        for (j = i; j > 0 && arr[j - 1] > temp; j--)
        {
            arr[j] = arr[j - 1];
        }
        arr[j] = temp;
    }
}

int main()
{
    int arr[10] = {5, 3, 7, 6, 1, 9, 0, 2, 8, 4};

    InsertionSort(arr, 10);

    for (int i = 0; i < 10; i++)
    {
        printf("%d ", arr[i]);
    }

    return 0;
}

결과

0 1 2 3 4 5 6 7 8 9