삽입 정렬(Insertion sort)

정렬하는 방법은 정렬하지 않는 부분 집합에서 하나의 원소를 꺼내서 정렬된 부분 집합에 삽입하는 방법이다.

시간복잡도
O(N^2)

Wiki에 잘 설명된 이미지가 있습니다.

마지막에 정렬되지 않은 숫자를 앞의 정렬된 숫자에 삽입 하는 과정이 있습니다.
위의 그림에서 보면 비교하다가 적절한 위치에 삽입이 되는데 이과정은 하나씩 swap함으로서 이루어 집니다.
따라서 Pseudocode는 아래와 같습니다.

for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

65318724 를 정렬하는 과정 코드 입니다.

C, pasted just now: 

#include <stdio.h> int data[]={6,5,3,1,8,7,2,4}; int N = 8; void print() { int i; for(i=0;i<N;i++){ printf("%d ",data[i]); } printf("\n"); } int insert_sort(int data[],int N) { int i,j,temp; for(i=1;i<N;i++){ print(); for(j=i;j>0;j--){ if(data[j]<data[j-1]){ //swap temp = data[j]; data[j] = data[j-1]; data[j-1] = temp; } } } return 0; } int main() { insert_sort(data,N); print(); return 0; }

Output:

6 5 3 1 8 7 2 4 5 6 3 1 8 7 2 4 3 5 6 1 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 8 7 2 4 1 3 5 6 7 8 2 4 1 2 3 5 6 7 8 4 1 2 3 4 5 6 7 8