셀 정렬 - shell sort

셀 정렬 은 축소 증 량 정렬 법 이 라 고도 부 르 는데 D. L. Shell 이 1959 년 에 제기 한 것 이다.
알고리즘 설명:
먼저 하나의 요소 간격 수 gap 를 확정 한 다음 에 정렬 에 참가 하 는 서열 을 이 간격 수 에 따라 첫 번 째 요소 부터 여러 개의 키 서열 로 나 누 었 다. 즉, 모든 위 치 를 gap 로 구분 하 는 요 소 를 하나의 키 서열 로 보고 각 키 서열 에서 특정한 정렬 알고리즘 으로 정렬 한 다음 에 간격 수 를 줄인다.그리고 전체 서열 을 새로운 간격 수 를 여러 개의 하위 서열 로 나 눈 다음 에 하위 서열 을 정렬 한 다음 에 간격 수 gap 를 줄 입 니 다. gap = 1. 예 를 들 어:
입력 데이터:
a0 = 5. a1 = 12, a2 = 3, a3 = 45, a4 = 76, a5 = 98, a6 = 90, a7 = 12, a8 = 9, a9 = 66, a10 = 35, a11 = 99, a12 = 10;
첫 번 째 정렬 의 gap = 5, 정렬 알고리즘 을 삽입 하여 gap 로 구 분 된 하위 배열 을 정렬 합 니 다: (a0, a5, a10), (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9)
정렬 결과:
a0 = 5, a1 = 12,  a2 = 3,  a3 = 9, a4 = 76, a5 = 35,  a6 = 90,  a7 = 10,  a8 = 45, a9 = 66, a10 = 98,  a11 = 99,  a12 = 12
두 번 째 정렬 의 gap = 3, 정렬 알고리즘 을 삽입 하여 gap 로 구 분 된 하위 배열 을 정렬 합 니 다: (a0, a3, a6, a9, a12), (a1, a4, a7, a10), (a2, a5, a8, a11)
정렬 결과:
a0 = 5, a1 = 10,  a2 = 3,  a3 = 9, a4 = 12, a5 = 35,  a6 = 12,  a7 = 76,  a8 = 45, a9 = 66, a10 = 98,  a11 = 99,  a12 = 90
세 번 째 정렬 의 gap = 1, 전체 배열 에 정렬 삽입
이상 의 분석 을 통 해 알 수 있 듯 이:
1. gap 의 값 을 x 로 설정 하면 gap 로 구 분 된 하위 배열 에 gap 개가 있 습 니 다. 이 하위 배열 에 정렬 알고리즘 을 삽입 하여 정렬 해 야 합 니 다.
2. 하위 서열 에 대한 정렬 로 인해 요소 간 의 교환 간격 이 매우 크기 때문에 이 정렬 방법 은 불안정 한 정렬 방법 이다.
의사 코드 먼저 보기:

//gaps           gap，     1
for gap in gaps
    for (i = 0; i < gap; ++i)      //i        gap           
        //                   
        for(j = i + gap; j < n; ++j)    //j                  
            k = j - gap;
            temp = array[j];
            if(k >= i and temp < array[k])
                array[k + gap] = array[k]
                k -= gap
            array[k + gap] = temp

아래 코드 는 제 가 C 언어 로 쓴 것 입 니 다. 제 가 여기 서 가 져 온 gap = n, 그리고 gap/= 2, gap = 1 까지 입 니 다.

#include <stdlib.h>
#include <stdio.h>

void print_array(int array[], int size)
{
    int i;
    for( i = 0 ; i < size ; ++i )
    {
        printf("%d ", array[i]);
    }
    printf("
");
}

void insertSort(int array[], int first, int n, int gap)
{
    int i, j, temp;
    for( i = first + gap ; i < n ; i += gap )
    {
        j = i - gap;
        temp = array[i];
        while( j >= first && temp < array[j] )
        {
            array[j + gap] = array[j];
            j -= gap;
        }
        array[j + gap] = temp;
    } 
}

void shellSort(int array[], int n)
{
    int i, j, gap = n;
    while( gap > 1 )
    {
        gap = gap / 2;
        for( i = 0 ; i < gap ; ++i )
        {
            insertSort(array, i, n, gap);
        }
        //print_array(array, n);
    }
}

int main()
{
    int array[] = {5, 12, 3, 45, 76, 98, 90, 12, 9, 66, 35, 99, 10};
    int size = sizeof(array) / sizeof(int);
    shellSort(array, size);
    print_array(array, size);
}

위의 셸 정렬 인 코딩 은 엄격하게 알고리즘 사고방식 에 따라 작 성 된 것 으로 사실은 다음 과 같은 인 코딩 으로 대체 할 수 있 으 며 구체 적 으로 설명 하지 않 습 니 다.

void shellSort(int array[], int n)
{
    for(int gap = n/2; gap > 0; gap /= 2)
        for(int i = gap; i < n; ++i)
        {
            int temp = array[i];
            int j = i - gap;
            while(j >= 0 && temp < array[j])
            {
                array[j+gap] = array[j];
                j -= gap;
            }
            array[j+gap] = temp;
        }
}