(정렬) 삽입 정렬

pseudo code

입력: 크기가 n인 배열 A
출력: 정렬된 배열 A

for i = 1 to n-1 {
	CurrentElement = A[i]
    j <- i-1
    while(j >= 0) and (A[j]>CurrentElement){
    	A[j+1] = A[j]
    	j <- j-1
    }
    A[j+1] <- CurrentElement
}
return A

c 코드

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

void swap(int* n1, int* n2) {
	int tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

void InsertionSort(int* A, int n) {
	int left = 0;
	for (int i = 1; i < n;i++) {
		left = A[i];
		int j = i - 1;
		while (j >= 0 && A[j] > left) {
			A[j + 1] = A[j];
			j = j - 1;
		}
		A[j + 1] = left;
	}
}

실행시간

8개 : 0.000

10,000개 : 0.045

100,000개 : 4.515

600,000개 : 161.678

1,000,000개 : 449.955