삽입정렬(insertion sort)

 

 

 

 

 

 

 

Name	Best	Avg	Worst	Run-time (int 60,000) sec
버블정렬	n^2	n^2	n^2	22.89
선택정렬	n^2	n^2	n^2	10.84
삽입정렬	n	n^2	n^2	7.43
셀정렬	n	n^1.5	n^2	0.05
퀵정렬	nlog₂n	nlog₂n	n^2	0.01
힙정렬	nlog₂n	nlog₂n	nlog₂n	0.03
병합정렬	nlog₂n	nlog₂n	nlog₂n	0.02

#include<stdio.h>
#define MAX_SIZE 5

void insertion_sort(int list[], int n)
{
	int i, j, key;

	for (i = 1; i < n; i++)
	{
		key = list[i];

		for (j = i - 1; j >= 0 && list[j] > key; j--)
		{
			list[j + 1] = list[j];
		}

		list[j + 1] = key;
	}
}



int main()
{
	int i;
	int n = MAX_SIZE;
	int list[] = { 8,5,6,2,4 };

	insertion_sort(list, n);

	for (i = 0; i < n; i++)
	{
		printf("%d", list[i]);
	}
}