Shell Sort

/*
shell sort사용 예제.
datain()함수로 생성한 data를 shell_sort()함수를 이용해서 정렬.
*/

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

void datain(int *, int); //데이터를 입력할 함수를 선언한다.
void shell_sort(int *, int); //shell 소트할 함수를 선언한다.

void main(void)
{
int n, i;
int *data; //data형을 integer형으로 선언한다.

while(1)
{
printf("input data number : ");
scanf("%d", &n); //데이터의 갯수를 받아들인다.

if(n == 0) //n = 0 이면 프로그램을 종료시킨다.
break;

data = (int *) malloc (sizeof(int) * (n+1)); //data를 integer형으로 n+1만큼 저장할수 있도록 한다.

datain(data, n); //데이터를 n개 만큼 저장할수 있도록 datain을 호출한다.

for (i = 1; i <= n; i++) //입력된 데이터를 화면에 출력한다.
printf("%8d", *(data+i));
printf("\n\n");

shell_sort(data, n); //shell소트하기 위해 shell함수를 호출한다.

for (i = 1; i<= n; i++) //소트된 데이터를 화면에 출력한다.
printf("%8d", *(data+i));
printf("\n\n");

free(data); //메모리에 할당된 영역을 지워버린다.
}
}

void datain(int *a, int n) //datain을 정의한다.
{
int i;

for(i = 1; i <= n; i++) //a+1번째에 0부터 400000까지 임의의 수를 입력한다.
*(a+i) = rand() % 400000;
}

void shell_sort(int *a, int n) //shell_sort함수 정의
{
int inc, temp, j = 0, i; //inc는 증가치, temp는 SWAP을 하기 위한 임시 저장공간,
//j, i, z 을 integer형으로 선언한다.
inc = n / 2; //증가치를 설정한다.

while(inc > 0) //증가치가 0보다 크면 수행한다.
{
for(i = inc+1; i <= n; i++) //inc+1부터 n까지 수행한다.
{
j= i - inc;
while(j > 0)
{
if( *(a+j) > *(a+j+inc) ) //a+j > a+j+inc 이면 데이터를 서로 바꿔준다.
{
temp = *(a+j);
*(a+j) = *(a+j+inc);
*(a+j+inc) = temp;
j = j - inc;
}
else //아니면 j = 0 을 넣어준다.
j = 0;
}
}
inc = inc / 2; //증가치를 재설정해준다.
}
}