작동 원리 : Insertion Sort 의 발전된 형태. 바로 전 원소와 비교하는 것이 아니라 h만큼 떨어진 원소와 비교한다. 일반적으로 h = 3 * h + 1 수열을 많이 사용한다.
시간복잡도 : O(n^1.5)
•
Required Function : swap
void swap(int *dest, int *src)
{
int tmp;
tmp = *dest;
*dest = *src;
*src = tmp;
}
C
복사
C++, C
void shell_sort(int *arr, int length)
{
int h = 1;
while(h < length / 3)
h = 3 * h + 1;
while(h >= 1)
{
for (int i = h; i <length ; i++)
for (int j = i; j >= h && arr[j] < arr[j - h] ; j -= h)
swap((arr + j), (arr + j - h ));
h /= 3;
}
}
C
복사
