[알고리즘 개념] Shell Sort

Shell Sort란?

• Insertion Sort를 기반으로 합니다.
• 서로 멀리 떨어져 있는 순자들을 정렬(insertion sort로)하기 시작하여 점점 두 숫자들 사이의 거리(gap)을 좁혀서 정렬합니다.
• 최종적으로 gap=1이 되면, 원래의 insertion sort를 실행하는 것과 동일합니다.
• Not stable하며 In-place 알고리즘 입니다.
• Gap, Gap Sequence
  • Gap
    • 정렬할 원소들이 떨어져 있는 거리입니다.
    • 처음에는 큰 gap을 사용하여 시작하지만, 점점 작게 만들고, 최종적으로는 1이됩니다.
  • Gap Sequence
    • 주어진 시작 숫자부터 gap만큼 떨어진 모든 숫자들의 집합입니다.
    • 같은 gap sequence에 속하는 숫자들을 insertion sort로 정렬합니다.
• Pass
  • 주어진 gap에 대하여 같은 gap을 가지는 모든 gap sequence에 insertion sort를 실행합니다.

Shell sort 코드

#include <stdio.h>
#define MAX_SIZE 1000
void ShellSort(int a[], int n);
int main()
{
    int numTestCases;
    scanf("%d", &numTestCases);
    for (int i = 0; i < numTestCases; ++i)
    {
        int num;
        int a[MAX_SIZE];
        scanf("%d", &num);
        for (int j = 0; j < num; j++)
            scanf("%d", &a[j]);
        ShellSort(a, num);
        printf("\n");
    }
    return 0; 
}
void swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp; 
}
/* Shell Sort 함수 */
void ShellSort(int a[], int n)
{
    int countCmpOps = 0; // 비교 연산자 실행 횟수 
    int countSwaps = 0; // swap 함수 실행 횟수
    int i,j;
    int shrinkRatio = 2;
    int gap = int(n/shrinkRatio);
    while(gap >0)
    {
        for(i = gap;i<n;i++)
        {
            int tmp = a[i];
            for(j = i;(j>=gap)&&(a[j-gap] > tmp); j -= gap)
            {
                a[j] = a[j-gap];
                countSwaps ++;
                countCmpOps ++;
            }
            a[j] = tmp;
            if (j >= gap){
            countCmpOps ++ ;
            }
        }
        gap /= shrinkRatio;
    }
    // Shell sort 알고리즘 구현
    printf("%d %d ", countCmpOps, countSwaps);
    return;
}