[Algorith] 쉘 정렬 (Shell Sort)

Bing-O 표기법에 의한 O( N (logN)^2 ) 이다.
퀵 정렬에 가까운 성능을 보인다.

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

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

// 함수의 프로토타입

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

int Buf[MAX];

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

	printf("정렬 후 데이터\n");
	ShellSort();
	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 ShellSort(void) // 정렬 함수
{
	int i, array_index, h, array_tmp; // array_index는 리스트의 배열 번호를, array_tmp는 배열 원소의 값을 임시 저장한다.

	for(h=1; h < MAX; h=3*h+1);
	for( ; h>0; h /=3) // h가 10이라면 0과 10의 인덱스의 원소값 교환 후 i++로 인해 1과 11의 인덱스의 원소값을 비교하는 식으로 간다.
	{
		for(i=h; i<MAX; i++)
		{
			array_tmp=Buf[i];
			array_index=i;
			while(array_index >=h && Buf[array_index-h] > array_tmp)
			{
				Buf[array_index] = Buf[array_index-h];
				array_index-=h;
			}
			Buf[array_index]=array_tmp;
		}
	}
}

void DisplayBuffer(void)
{
	int i;

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