[ 정렬 ] 쉘 정렬 (Shell Sort) (C++)

이번 글에서는 쉘 ? 셸 ? 정렬(Shell Sort)에 대해서 다뤄보겠다.

먼저 Shell정렬이 어떤 정렬인지에 대해서 간략하게 알고 들어가보자.

Shell정렬은 '삽입정렬(Insertion Sort)' 에서 최악의 경우에 너무 오래걸리는 문제점을 보완하기 위해서 만들어진

정렬방식이다.

아직 삽입정렬에 대해서 잘 모른다면 아래의 글을 읽고 오도록 하자.

[ InsertionSort(삽입정렬) 알아보기(Click) ]

Shell정렬의 기본 원리는 삽입정렬과 똑같다. 동작하는 방식은 똑같은데, 비교하는 횟수가 삽입정렬보다 훨씬 적다.

어떤 방식인지 구체적으로 한번 알아보자.

삽입정렬에 대한 글을 읽고 왔거나 이미 알고 있다는 가정하에 삽입정렬의 동작원리에 대해서 간단하게 설명하자면

와 같은 배열이 있을 때, '1'번 Index부터 앞 방향으로 진행하면서 값을 정렬시키는 방식이었다.

2번 Index에 존재하는 '1'의 값을 예시로 들자면 다음과 같이 실행된다.

위와 같이 진행되는데, 삽입정렬의 가장 큰 문제점은 최악의 경우에 시간복잡도가 만큼 걸린다는 것이었다.

Shell 정렬은 이렇게 삽입정렬로 정렬할 시, 최악의 경우 너무 오래걸리는 문제점을 보완하기 위한 방법이다.

그 방법은 다음과 같다.

삽입정렬의 방식으로 정렬을 하는데, 가장 큰 차이가 '일정한 간격으로 배열을 쪼갠 것 처럼 보면서 쪼갠 배열들을 정렬'

하는 것이다. 절대로 이해할 수 없는 말이다. 왜냐하면 본인도 써놓고 무슨 말인지 모르겠기 때문이다.

그림을 하나하나씩 보면서 해결해보자. 다음과 같은 배열이 있다.

그렇다면 일단 말 그대로 위의 배열을 한번 쪼갠 것 처럼 바라봐 보자.

일단, 가장 쉽게 절반으로 딱 나눈다고 생각해보자. 그렇다면 배열이 어떻게 될까??

실제로 배열이 이렇게 나뉘지는 않는데, 이렇게 배열을 바라볼 수 있을 것이다.

이 후에 무슨 값을 비교할까?! 다시 삽입정렬로 돌아가보자. 삽입정렬에서는 '1'번 Index부터 시작하면서 현재 시작 값을 임시 변수에 저장해 주고 '앞 방향'으로 탐색을 진행했었다. 똑같다. 이 원리가 그대로 적용되는데, 다만 지금 위에 보면 2개의 배열이 있으니까 그 2개의 배열에서 각각의 위치에 맞게 '앞 방향' 으로 탐색을 해주면 된다.

즉, 색깔로 표시하면 다음과 같다.

위의 그림에서 색깔이 의미하는 것은 바로 비교해야 될 대상이라는 것이다.

삽입정렬과 한번 비교해보자. 삽입정렬에서는 위의 그림에서 오른쪽 배열의 가장 왼쪽 값인 '2'를 시작점으로 탐색을 진행한다고 치면, 그 앞에 있는 '15, '1', '4', '7', '6' 을 비교해야 했다. 아 물론 중간에 2보다 더 작은값인 1이 나와서 중간 과정에서 break가 되겠지만 뭐 대충 말하자면 그런 방식이었다. 하지만, 쉘 정렬에서는 나눈 갯수만큼 뛰어넘고 비교를 하게 된다.

위의 배열을 보면 처음 크기는 10, 우리는 이 배열을 반 씩 나눈 것 처럼 바라보기 위해서 크기를 5 씩 가지도록 만들어 주었다. 즉, '앞 방향으로 5칸씩 뛰어 넘으면서 비교' 를 한다는 것이다.

그렇게 되면, 가장 먼저 '6'과 '2'를 비교할 것이다. '2'가 더 작기 때문에 더 앞으로 와야 하고, 삽입정렬의 방식과 마찬가지로 다음과 같은 순서로 위의 배열이 정렬된다.

위의 2번의 과정이 이해가 잘 안된다면 삽입정렬을 다시 한번 보고 오도록 하자 ! 쉘 정렬 자체가 삽입정렬의 정렬 방식을 기반으로 하되, 한 칸씩 비교하는 것이 아닌 특정 칸 수 만큼 뛰어 넘으면서 비교를 하는 방식이기 때문이다.

위와 같은 방식으로 색깔별로 정렬을 하게 되면 아마 다음과 같이 정렬될 것이다.

원본의 배열 상태를 본다면 다음과 같다.

그럼 이 상태에서는 어떻게 할까?? 2로 나눠봤으니 이제는 그 2를 2로 한번 더 나눈 4로 한번 나눠보자 !

그렇게 되면 배열을 다음과 같이 나눈 형태로 바라볼 수 있게 된다. 10을 4로 나누게 되면 2.5가 나오게 되고 간격은 뭐 대략

2칸의 간격을 갖는 배열로 나눈다고 생각을 해보자.

즉 우리는 배열을 실제로 나누지는 않았지만 위의 그림과 같이 배열을 바라보게 될 것이다.

그렇다면 이제 또 색깔을 칠해봄으로써 어떤 값들을 비교해야 되는지 알아보자. 색을 칠한다면 아래와 같이 칠할 수 있다.

왜 위와 같이 색깔을 칠할 수 있을까?? 간격이 2칸을 갖기 때문이다 !

그렇다면 이제 빨강색 끼리 비교를 한번 해보자 !

계속 생각을 해줘야 한다. 삽입정렬 처럼 우리는 '1'번 Index부터 진행을 한다.

즉, 빨강색을 비교하는데 제일 앞에 '2'는 넘기고 두 번째 빨강색인 '4'부터 진행을 하는 것이다.

'4'와 '2'를 비교해보자. 먼저 '4'를 임시 저장 변수 Temp에 저장해주고 비교 !

'4'가 더 크네? 값의 삽입이 일어나지 않는다. 그대로 break.

그 다음은 어디로 갈까?? 삽입정렬에서는 그 다음 Index로 그냥 넘어갔다. Shell 정렬에서는??

그 다음 빨강색 칸으로 넘어가면 된다. 즉 '10'을 보게 되는 것이다.

'10'과 '4'를 비교해보자. 10을 먼저 임시저장변수 Temp에 저장해주고 비교 시작 !

10이 더 크기 때문에 삽입의 과정이 일어나지 않는다. 그대로 break.

그 다음은 '8'을 보자. 8을 임시저장변수 Temp에 저장해주고 비교 시작 !

8과 10을 비교했더니 10이 더크네? 그러면 10을 그대로 그 다음 칸(그 다음 빨강색 칸)에 삽입 후 탐색 진행.

즉, 아래와 같은 상황이 될 것이다.

탐색을 계속 진행해보자. '8'과 '4'를 비교했더니, '8'이 더 크므로 그대로 break. 이 후, 삽입정렬에서 했던 것과 같이

Index값 ++ 후 Temp값을 그 자리에 삽입을 해주게 되면 다음과 같아진다.

( ※ 계속해서 '삽입정렬과 같이', '삽입정렬처럼' 이라는 말이 나오는데, 삽입정렬을 이해했다면 이해할 수 있는 문구들이다 !)

마지막 '3'을 시작해보자. 뭐, 똑같이 진행한다면 아래와 같은 결과를 얻을 수 있을 것이다.

그 다음 과정은 뭘까?? 파랑색도 위와 같이 똑같이 진행하면 되는 것이다. 파랑색도 똑같이 진행한다면 다음과 같은 결과를

얻게 될 것이다.

이를 하나의 배열처럼 다시 보기 위해서 합쳐진 꼴로 만들어보면 다음과 같아진다.

아직도 정렬이 되지 않았다. 그렇다면 더 작게 나눠봐야 겠네?? 그럼 이제 2, 4로 나눠봤으니 8로 나눠보자...

10 을 8로 나눠보면 대략 1.xxx 이고 약 1칸씩 나누면 될 것이다. 근데,.... 1칸씩 나눌거면 결과적으로 삽입정렬과 똑같은

형태이지 않을까?? 맞다. Shell정렬도 최종적으로는 삽입정렬처럼 정렬하는 방식을 한 번은 사용해야 될 것이다.

그렇다면 이게 왜 시간을 줄일 수 있는 것일까???

삽입정렬에서 최악의 시간이 걸린 이유는, 모든 Index들에서 비교할 수 있는 최대 횟수를 비교함으로써 그만큼의 시간이

걸리게 되었다. 그렇다면 위의 상태는 ??

보면 알겠지만 정확한 정렬은 되어있지 않지만, 대충 작은 값들이 앞쪽에 큰 값들이 뒤쪽에 포진되어 있음을 확인할 수가 있다. 심지어, 위의 경우는 재수가 좋아서 7 8 9 10 15 는 이미 정렬이 완성되어 있는 상태이다.

즉 ! 아무리 삽입정렬의 과정을 한다고 하더라도, 절대로 삽입정렬이 겪었던 최악의 경우가 발생하지 않는다는 것이다.

이러한 점에서 Shell정렬이 삽입정렬의 시간이 오래걸리는 문제점을 해결할 수 있는 것이다.

실제 구현된 코드를 주석 설명과 함께 보면서 어떻게 동작되는지 알아보도록 하자.

void Shell_Sort()        // Shell Sort() 함수.
{
    for (int Interval = MAX / 2; Interval > 0; Interval = Interval / 2)    // 2로 나눈 값부터 0보다 클 때까지 계속

                                                                                              // 2로 나눠주면서 비교 간격 설정 !
    {
        if ((Interval % 2) == 0) Interval++;                // 홀수로 만들어주기 (밑에서 설명)
        for (int i = 0; i < Interval; i++)                     // 간격만큼만 반복. (밑에서 설명)
        {
            Interval_Sort(i, MAX - 1, Interval);            // Interval Sort 함수 호출.
        }
    }
}

위의 코드를 보면서 갑자기 뜬금 없는 부분이 몇가지가 있었다. 먼저 가장 바깥쪽 for문은 이해했을 것이다. 2로 계속 나눠주면서 간격을 설정해주는 것이라는 것을. 그런데 갑자기 '홀수로 만들기' 라는 부분이 있다.

이 부분에 대해서 약간의 설명을 하자면 본인도 사실 증명할 수 없고 깊게 알지 못하는 내용인데, Shell 정렬은 일단 나누는

간격에 의해서 시간복잡도가 조금 갈리는 편이라고 한다. 그래서 이 시간복잡도를 조금이라도 높이기 위해서는 간격을

'홀수'로 만들어주는 것이 좋다고 한다. 본인도 왜 그러는지 사실 잘 모르겠다. 무튼 그렇다고 한다.... 그래서 위와 같이 간격을 2로 나누면서 설정해주되, 짝수일 경우 +1을 통해서 홀수로 만들어 주는 것이다.

그리고 '간격만큼만 반복' 하는 for문이 있다. 이 for문이 무엇을 하는 것일까?? 쉽게 말하면 우리가 위에서 봤던

빨강색으로 칠해진 배열을 계산하는것과 파랑색으로 칠해진 배열을 계산하는 것이다.

이 경우 간격이 2였었다. 즉, 우리는 '빨강색으로 칠해진 배열들 계산' 1번, '파랑색으로 칠해진 배열들 계산' 1번

총 2번의 계산만 해주면 되는 것이다. 따라서, 이 과정을 위해서 '간격 만큼만 반복'해주는 for문을 통해서 또 다른 함수를

호출해주게 된다. 그렇다면 이제 그 '또다른 함수'에 대해서 보자.

void Interval_Sort(int Start, int End, int Gap)   
{
    for (int i = Start + Gap; i <= End; i = i + Gap)   
    {
        int Temp = Arr[i];
        int j;
        for (j = i - Gap; j >= Start ; j = j - Gap)
        {
            if (Arr[j] > Temp) Arr[j + Gap] = Arr[j];
            else break;
        }
        Arr[j + Gap] = Temp;
    }
}

위의 코드에서는 주석으로 달기에는 설명할 내용이 너무 많아서 따로 이렇게 글로 설명하겠다.

가장 먼저 제일 위에 있는 for문에 들어가는 변수부터 맘에 드는 꼴이 아니다. 하지만, 생각을 하고 이해를 하면 쉬워진다.

우리는 삽입정렬을 할 때 '0'번 Index는 건너뛰고, '1'번 Index부터 계산을 했다.

Shell정렬도 마찬가지이다. 빨강색으로 칠해진 배열을 계산할 때, 제일 앞에 칠해진 빨강색 배열은 넘겨버리고, 두 번째로 칠해진 빨강색 배열부터 보면 되는 것이다. 즉, 시작점이 삽입정렬 처럼 '1'이 아닌, '첫번째로 칠해진 빨강색 배열 + 간격' 번 Index

를 가지는 배열이 시작점인 것이다.

그렇다면 탐색은?? 똑같이 앞방향인데 같은 색으로 칠해진 배열만 비교한다고 했다. 따라서, 안에 있는 for문의 값이

저렇게 설정되는 것이다. 삽입정렬을 제대로 이해하고 있다면 보다 수월하게 이해할 수 있을 것이다.

# 시간복잡도

- 본인도 증명은 하지 못하겠고 계속해서 검색해보면서 알아낸 내용 수준에서만 적어보겠습니다,....

- Shell정렬의 경우 나누는 간격 값에 대해 시간에 크게 영향을 미친다고 한다. 이 나누는 간격에 의해서 최악의 경우

  의 시간복잡도를 갖는다고는 한다. 그렇다면 ! 이게 삽입정렬보다 뭐가 더 빠르다는 것일까??

   Shell정렬 자체가 그리 빠르다는 것은 아니다. 다만, 삽입정렬보다 평균적인 경우 보다 더 빠르다는 것이다.

   삽입정렬의 경우, 최선의 경우 을 갖게 되고 최악의 경우는 을 갖게 된다.

   그렇다면 일반적인 경우는?? N보다는 많이 걸리고 N^2 보다는 덜 걸리기 때문에 최악의 상황을 대비해서

   이 걸린다고 표현을 한다.

   하지만, Shell정렬의 경우, 이 일반적인 경우에 정도가 걸린다고 한다.

   즉, N의 1승보다는 더 걸리긴 하지만, N의 제곱보다는 작게 걸린다는 것이다. 이러한 점에서 삽입정렬보다 빠르다고

   표현한다.

   즉, Shell정렬의 경우 최악 = , 일반적인 경우 = , 최선의 경우 = 이

   걸리게 된다.

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<ctime>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
bool Flag[301];
 
void Print()
{
    cout << "##########################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", Arr[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "##########################################################################################################" << endl;
    cout << endl;
}
 
void Interval_Sort(int Start, int End, int Gap)
{
    for (int i = Start + Gap; i <= End; i = i + Gap)
    {
        int Temp = Arr[i];
        int j;
        for (j = i - Gap; j >= Start ; j = j - Gap)
        {
            if (Arr[j] > Temp) Arr[j + Gap] = Arr[j];
            else break;
        }
        Arr[j + Gap] = Temp;
    }
}
 
void Shell_Sort()
{
    for (int Interval = MAX / 2; Interval > 0; Interval = Interval / 2)
    {
        if ((Interval % 2) == 0) Interval++;
        for (int i = 0; i < Interval; i++)
        {
            Interval_Sort(i, MAX - 1, Interval);
        }
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < MAX; )
    {
        Arr[i] = (rand() % 300) + 1;
        if (Flag[Arr[i]] == false)
        {
            Flag[Arr[i]] = true;
            i++;
        }
    }
    
    cout << "[ Initialize Array State ] " << endl;
    Print();
    Shell_Sort();
    cout << "[ After Sort Array State ] " << endl;
    Print();
 
    return 0;
}