[알고리즘] 삽입 정렬

삽입 정렬 ( 출처 : https://ko.wikipedia.org/wiki/삽입_정렬 )

 

삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

삽입 정렬의 구체적인 개념

삽입 정렬은 두 번째 자료부터 시작해 그 앞 ( 왼쪽 )의 자료들과 비교해 삽입할 위치를 지정한 후 자료를 뒤로 옮기고

지정한 자리에 자료를 삽입해서 정렬하는 알고리즘이다.

 

void InsertionSort(int list[], int n)
{
	for (int i = 1; i < n; i++)
	{
		int j;
		int key = list[i];

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

		list[j + 1] = key;
	}
}