쉘 정렬 (Shell sort)

▷ 쉘 정렬 (Shell sort)

쉘 정렬은 삽입 정렬이 어느 정도 정렬된 리스트에 대해서는 대단히 빠른것에 착안한 방법이다.

쉘 정렬은 삽입 정렬과는 다르게 전체의 값을 한 번에 정렬하지 않는다.

쉘 정렬은 일정한 기준에 따라 값을 분류한 후 부분 리스트들을 만들고 그 부분 리스트들에 대해서 삽입정렬을 실행한다.

그리고 각 정렬될 리스트들을 모아서 하나로 만든 후 삽입정렬을 실행한다.

삽입 정렬은 이미 정리되어 있는 데이터에 대해서는 연산을 하지 않기 때문에 부분을 미리 정렬하고 전체를 정렬할 경우

연산이 줄어들기 때문에 순수한 삽입 정렬보다는 효율이 좋다.

임의의 값을 정렬해보자.

정렬의 순서는 오름차순이다.

시작 : 7 2 4 1 8 3 5 9 6 10

1. 간격을 5로 잡고 각 간격에 있는 숫자들을 각각 모아 삽입정렬로 정렬한다.

※ 간격은 자신의 마음대로 정해도 된다.

한 번 정렬된 결과.

2. 정렬이 끝났으면 간격을 2로 나눈다.

※ 5를 나눴을 때 2.5 하지만 소수점 자리는 버린다.

3. 간격이 2로 바뀌었으므로 2간격으로 떨어진 숫자들을 모아 삽입정렬한다.

두 번째 정렬된 결과.

4. 정렬이 끝났으면 간격을 2로 나눈다.

5. 간격이 1로 바뀌었으므로 전체에 대한 삽입정렬을 실행한다.

6. 간격이 1보다 작아지면 반복을 중지한다.

7. 정렬 완료.

Code

#include <iostream>
using namespace std;
 
#define MAX            5
 
void ShellSort( int *Number );
void main()
{
    int Number[MAX] = {7, 3, 9, 4, 1};
 
    ShellSort( Number );
 
    for(int i = 0; i < MAX; i++)
        printf("%d \n", Number[i] );
}
 
void ShellSort( int *Number )
{
    int Gap = 5;
    int Value, i, j;
 
    while( Gap > 0 )
    {
        for(i = Gap; i < MAX; i++)
        {
            Value = Number[i];
            for(j = i - Gap; j >= 0; j -= Gap)
            {
                if(Value < Number[j])
                    Number[j + Gap] = Number[j];
                else
                    break;
            }
            Number[j + Gap] = Value;
        }
        Gap /= 2;
    }
}

결과.