[Algorith] 삽입 정렬 (Insertion Sort)

정렬 전 3  7  9  1  2  
1차 정렬 3  7  9  1  2
2차 정렬 3  7  9  1  2
3차 정렬 1  3  7  9  2
4차 정렬 1  2  3  7  9

 

비교 횟수는 데이터 수와 같다. 최악의 경우엔 N(N-1)/2 의 계산이 필요하다.
또한 데이터의 이동 횟수도 N(N-1)/2의 계산이 나온다

따라서 정렬이 잘된 리스트를 가지고 삽입  정렬을 하면 선택 정렬에 비해 빠를 수 있다.
왜냐면 삽입 정렬의 비교가 비교적 선택 정렬보다 적을 수 있기 때문이다.
그래서 정렬이 잘 되어 있다면 O(N)에 가까운 계산이 나올 수 있다.

다만 정렬이 안된 상태라면 선택 정렬이 빠를 수 있다.

Big-O 표기법의 의한 O(N^2)이다.

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

#define MAX 100
#define TRUE 1
#define FALSE 0

// 함수의 프로토타입

void MakeRandomNumber(void);
void InsertionSort(void);
void DisplayBuffer(void);
int IsNumberExit(int, int);

int Buf[MAX];


void main()
{
	printf("정렬할 데이터의 초기화\n");
	MakeRandomNumber();
	DisplayBuffer();

	printf("정렬 후 데이터\n");
	InsertionSort();
	DisplayBuffer();
	printf("\n");

}

//정렬할 데이터의 초기화
void MakeRandomNumber(void)
{
	int i, Num;
	i=1;
	Buf[0]=100;
	while(i < MAX)
	{
		Num = rand() % MAX;

		if(!IsNumberExit(Num, i))
		{
			Buf[i]=Num;
			i++;
		}
	}
}

// 이미 생성된 값이 아닌지를 검사
int IsNumberExit(int number, int index)
{
	int i;

	for(i=1; i < index; i++)
	{
		if(Buf[i] == number)
		return TRUE;
	}
	return FALSE;
}

void InsertionSort(void) // 정렬 함수
{
	int i, j, dummy;

	for(i=1; i < MAX; i++)
	{
		dummy = Buf[i];
		j = i;
		while(Buf[j-1] > dummy && j > 0)
		{
			Buf[j] = Buf[j-1];
			j--;
		}
		Buf[j] = dummy;
	}
}

void DisplayBuffer(void)
{
	int i;

	for(i=0; i < MAX; i++)
	{
		printf("%4d", Buf[i]);
		if((i % 10) == 9 )
		printf("\n");
	}
	printf("\n");
}