[알고리즘/자료구조] 셸 정렬(Shell sort)

셸 정렬(Shell sort)

셸 정렬(영어: shell sort)은 가장 오래된 정렬 알고리즘의 하나이다. 이름은 1959년 이 방법을 발표한 창안자 도널드 셸의 이름을 따서 붙여졌다. 셸 정렬은 개념을 이해하고 구현하기는 쉬우나 시간복잡도 분석은 조금 복잡하다.

셸 정렬은 다음과 같은 삽입 정렬의 성질을 이용, 보완한 삽입정렬의 일반화로 볼 수 있다.

삽입 정렬은 입력되는 초기리스트가 "거의 정렬"되어 있을 경우 효율적이다.

삽입 정렬은 한 번에 한 요소의 위치만 결정되기 때문에 비효율적이다.

셸 정렬은 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일(subfile)로 쪼개서, 각 부파일에서 정렬을 수행한다. 즉, 매개변수 값에 따라 부파일(Subfile)이 발생하며, 매개변수값을 줄이며 이 과정을 반복하고 결국 매개변수 값이 1이면 정렬은 완성된다.

셸 정렬은 다음과 같은 과정으로 나눈다.

데이터를 십수 개 정도 듬성듬성 나누어서 삽입 정렬한다.

데이터를 다시 잘게 나누어서 삽입 정렬한다.

이렇게 계속 하여 마침내 정렬이 된다.

셸 정렬에서 데이터를 나누는 값(이하 N)은 보통 전체에서 2로 나누는 값으로 진행한다. 그러나 3을 나누고 1을 더하는 경우가 더 빠르다고 알려져 있다. 즉 N/2 보다는 N/3+1이 더 빠르다.

소스

/*
/*    
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*    
/*    2018 - 11 - 16
/*
*/
 
#include <iostream>
#include <stdio.h>
#include <conio.h>
 
using namespace std;
 
int Data[16] = {9, 19, 62, 5, 55, 33, 12, 23, 4, 123, 85, 1, 18, 6, 3, 11};
 
void print()
{
    cout << " Data Array is [ " ;
    for (int i = 0; i < 16; i++)
    {
        cout << Data[i] << " ";
    }
    cout << "] "<< endl;
}
 
void SortInsertion(int arr[], int first, int last, int gap)
{
    int key;
    int j;
    for(int i = first + gap; i<= last; i = i+gap)
    {
        key = Data[i];
 
        for(j = i-gap; j>= first && Data[j] > key; j = j-gap)
        {
            Data[j+gap] = Data[j];
        }
        Data[j+gap] = key;
    }
    print();
}
 
 
void SortShell(int arr[], int n)
{
    int gap;
 
    for(gap = n/2; gap > 0; gap = gap/2)
    {
        if((gap%2) == 0)
            gap++;
 
        for(int i = 0; i< gap; i++)
        {
            SortInsertion(arr, i, n-1, gap);
        }
    }
}
void main()
{
    int length = sizeof(Data) / sizeof(Data[0]);
    int i;
    SortShell(Data, length);
    getch();
 
}

결과화면

출처

https://en.wikipedia.org/wiki/Shellsort