[C] 쉘정렬 사용 예제

[C] 쉘정렬 사용 예제

삽입 정렬은 이미 정렬된 배열이나 대충 정렬된 배열에 대해서는 매우 뛰어난 성능을 보이지만 그렇지 않은 경우에는 속도가 매우 느리다. 이것은 삽입 정렬이 바로 인접한 요소와 비교를 하기 때문이다.

쉘 정렬은 이 같은 문제점을 해결하기 위해서 h만큼의 간격으로 떨어진 레코드를 삽입 정렬하는 방법이다.

쉘 정렬은 안정성이 없다

쉘 정렬은 h 값에 의해 성능이 좌우된다.

h = 3 * h +1  이 가장 효율이 좋다고 한다.

#include <stdio.h> #include <malloc.h> // 최대 효율 h 지정 h = 3*h+1 void shell_sort1(int a[], int n){     int i, j, k, h, v;     for (h = 1; h < n; h = 3 * h + 1);    // n보다 작은 h의 최대값을 찾는다.     for (h /= 3; h > 0; h /= 3){         for (i = 0; i < h; i++){             for (j = i + h; j < n; j += h){                 v = a[j];                 k = j;                 while (k>h - 1 && a[k - h] > v){                     a[k] = a[k - h];                     k -= h;                 }                 a[k] = v;             }         }     } }

쉘 정렬은 4중 루프로 구성되어 있어 속도가 매우 느릴 것 같지만, 속도면에서는 성능이 좋은 알고리즘이다.

* 일반화된 쉘 정렬

#include <stdio.h> #include <malloc.h> #include <memory.h> #include <string.h> void gen_shell_sort(void *base, size_t nelem, size_t width,     int(*fcmp)(const void*, const void*)){ int i, j, k, h;     void *v;     v = malloc(width);     for (h = 1; h < nelem; h = 3 * h + 1);     for (h /= 3; h > 0; h /= 3){         for (i = 0; i < h; i++){             for (j = i + h; j < nelem; j += h){                 memcpy(v, (char*)base + j*width, width);                 k = j;                 while (k>h - 1 && fcmp((char*)base + (k - h)*width, v) > 0){                     memcpy((char*)base + k*width, (char*)base + (k - h)*width, width);                     k -= h;                 }                 memcpy((char*)base + k*width, v, width);             }         }     }     free(v); }

출처: https://hyeonstorage.tistory.com/359?category=622873 [개발이 하고 싶어요]