insertion sort

삽입 정렬은 값이 정렬된 상태에서 값을 추가하는 방식이다.

배열에 5,  4, 3, 2, 1이 있을때 선택 정렬 순서는 다음과 같다.

Step-1: 4 5          array[1] 키로 삽입 했을때
Step-2: 3 4 5       array[2] 키로 삽입 했을때
Step-3: 2 3 4 5     array[3] 키로 삽입 했을때
Step-4: 1 2 3 4 5  array[4] 키로 삽입 했을때  

삽입정렬의 복잡도

최선 :
N

평균 및 최악 :
(N-1) + (N-2) + ... + 2 + 1 = (N-1) * N/2 = N(N-1) / 2

C 코드


void InsertionSort(int arr[], int count)
{
    int key = 0, m = 0;

    for (int n = 1; n < count; n++)
    {
        key = arr[n];
        m = n;

        //정렬된 상태에 키를 삽입한다.
        //예)  1, 2, 4, 5 배열에 3을 추가한다면 4, 5를 뒤로 밀어 낸다.
        while (m > 0 && arr[m - 1] > key)
        {
            arr[m] = arr[m - 1];
            m = m - 1;
        }

        arr[m] = key;
    }
}

Python 코드


def insertionSort(arr):
    for n in range(1, len(arr)):
        key = arr[n];
        m = n
        while m > 0 and arr[m-1] > key:
            arr[m] = arr[m-1]
            m = m - 1
               
        arr[m] = key
       
               
alist = [5, 4, 3, 2, 1]
insertionSort(alist)
print(alist)


소스 : InsertionSort.cpp    insertionSort.py

C 코드 참조)
https://ko.wikipedia.org/wiki/ 삽입_정렬
열혈강의 C로 만드는 자료구조와 적용 알고리즘 해설서

Python 코드 참조)
https://ko.wikipedia.org/wiki/ 삽입_정렬