쉘 정렬( shell sort )

일정한 간격을 기준으로 같은 위치에 있는 원소들끼리 묶음을 만들어서

묶음끼리 삽입정렬을 수행하고 간격 K가 1이 될때까지 정렬을 시행하는 것

간격 K=1일땐 일반 삽입정렬과 똑같은 알고리즘을 수행 하지만

간격을 줄여가면 이미 어느정도 정렬이 되어있기 때문에 원래의 삽입정렬보다 효과적이다.

쉘 정렬이 선택,버블,삽입에 비해 훨씬 빠르다.

ex)

44, 33, 22, | 11, 55, 66, | 88, 99, 100, | 111, 222

간격 K = 3 인 경우

묶음 1 : 44, 11, 88, 111

묶음 2 : 33, 55, 99, 222

묶음 3 : 22, 66, 100

#include <stdio.h>

void Print_Arr( int arr[], int size )

{

for( int i = 0 ; i < size ; i++ )

{

if( i < size ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Shell_Sort( int arr[], int size );

void main()

{

}

void Shell_Sort( int arr[], int size )

{

int i, j, k;

int i_Interval, i_MaxInterval = 1;

int temp;

while( i_MaxInterval * 3 + 1 > size )                

{

i_MaxInterval = i_MaxInterval * 3 + 1;        // interval 은 n= 3*n+1이 가장빠르다는 연구 결과가 있단다.

}

for( i_Interval = i_MaxInterval ; i_Interval > 0 ; i_Interval /= 3 )

{

for( i = 0 ; i < i_Interval ; i++ )

{

for( j = i + i_Interval ; j < size ; j+= i_Interval )

{

temp = arr[j];

k = j;

while( k > i_Interval - 1 && temp < arr[k-i_Interval] )

{

arr[k] = arr[k-i_Interval];

k -= i_Interval;

}

arr[k] = temp;

}

}

}

}