ShellSort

ShellSort 는 뭐라하지.. 조개껍질?? 은 아니고 창안자인 도널드 셸을 따서 이름 지었다고 한다.

원리

1. [InsertionSort]와 마찬가지로 현재요소의 제 자리를 찾는 과정이 필요하다.

2. 현재요소( current )가 현재요소 - H( current - H ) 보다 작다면 교환이 일어난다.(H는 H-Sequence)

특징

1. InsertionSort의 최대 장점인 거의 정렬된 배열의 경우 빠르다는 것을 잘 살린 알고리즘이다.

2. for문을 총 3중으로 사용하기 때문에 언뜻보면 O(n^3)으로 볼수 있다. 하지만 일정 Interval을 기준으로 jump하며 반복한다.

3. H-Sequence(= Interval)라고하는 개념을 통해 분할정렬한다.

4. 매우 먼 거리의 요소들을 한번에 가까운 거리로 옮기면서 정렬하기 때문에 교환이 적게 일어난다.

연산시간

1. 최악의 경우 :   = n(n-1) / 2 

2. O표기법으로는 O(n^2)이 된다.

코드

//SHELLSORT
 
void insertionSort(int* array, int size, int interval)
{
    for (int i = interval; i < size; i++)      // i == (1 ~ size)
    {
        int temp = array[i];                   // 현재값 저장
        int tempidx = i;                       // 현재 인덱스 저장
 
        for (int j = i; 0 <= (j - interval) && temp < array[j - interval]; j -= interval)  
        {                                      // j == (i ~ 0)                                 
            array[j] = array[j - interval];    // (j) < (j - interval)이면 교환
            tempidx = j - interval;
        }
        array[tempidx] = temp;                 // 값 대입 
    }
}
void ShellSort(int* array, int size)
{
    for (int h = size; 1 <= h; h /= 2)
    {
        insertionSort(array, size, h);         // h값을 인자로 넘긴다.
    }
}
int const MAX = 5;                     // Max 값
int g_arr[MAX] = {0, };                // 배열 초기화
   
int main()
{
    printf("========정렬전========\n");
    //AscendingNumber(g_arr, MAX);     // 순열 배열 생성
    //DescendingNumber(g_arr, MAX);    // 역순 배열 생성
    RandomNumber(g_arr, MAX);          // 랜덤 배열 생성
 
    PrintNumber(g_arr, MAX);           // 배열 출력
    printf("\n");
    clock_t start = clock();           // 시작 시간
    ShellSort(g_arr, MAX);             // ShellSort
    clock_t end = clock();             // 끝 시간
    
    printf("========정렬후========\n");
    PrintNumber(g_arr, MAX);           // 배열 출력
    printf("\nTime : %f\n", ((double)(end-start)) / CLOCKS_PER_SEC);
}
 

결과

시간

시간은 MAX 값 100,000 과  100,000,000으로 기준을 나누어 측정하였다.

요소 수 :           100,000               100,000,000   

랜덤 배열 :         0.036                      105
역순 배열 :         0.012                       17
순열 배열 :         0.0074                    13.6     

결론

InsertionSort를 변형하여 구현하였다.

구현하면서 느낀점은 InsertionSort의 단점을 상당부분 보안한 알고리즘이라는 것이다.(한번에 많은 이동을 한다는 점에서)

위의 코드와 결과를 보면 알수 있듯이, 구현은 간단하지만 성능은 무시할 수 없는 알고리즘이다. 

특히 역순이나 순열의 경우 QuickSort보다 빠른 속도를 보였다.

적절한 상황에 사용하면 좋은 정렬알고리즘이다.