Shell Sort

이 포스트는 삽입 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 저번에 적은 삽입 정렬에 관한 글이 있으니 참고하실 분은 참고하시면 됩니다.

2022.09.12 - [알고리즘] - 삽입 정렬(Insertion Sort)

Shell Sort

기존의 삽입 정렬은 정렬을 위해 배열 내의 원소 간 이동이 많이 발생한다는 단점이 생깁니다. 만일 정수형 배열에서 원소 '1'이 배열의 가장 끝에 있다고 해봅시다. 그럼 원소 '1'을 배열의 거의 앞에 놓기 위해 거의 모든 원소들이 한 칸씩 옆으로 이동하는 연산을 수행해야 합니다. Shell 정렬은 이러한 문제점을 개선하기 위해 생겼습니다.

Shell 정렬에서는 gap만큼 떨어진 원소들끼리의 삽입 정렬을 진행해서 적은 데이터의 이동으로 작은 값을 앞으로 당겨올 수 있다는 장점이 생깁니다. 따라서 gap을 얼만큼 설정하느냐가 shell sort의 효율성을 결정한다고 할 수 있습니다.

source: https://en.wikipedia.org/wiki/Shellsort#Gap_sequences

gap을 줄여가다보면 gap이 1일 때가 오는데 이는 기존의 삽입 정렬과 동일하게 진행됩니다.

정렬 과정

길이가 8인 정수형 배열({3, 8, 6, 5, 4, 4, 2, 1})을 정렬해봅시다. 먼저 초기의 gap을 설정하고 그리고 어떻게 줄여나갈지 결정해야 합니다. 여기서는 배열의 길이를 2로 나눈 값(=4)을 gap으로 결정하고, 2씩 나누면서 gap을 줄여보겠습니다.

 

gap이 4일 때의 shell sort과정을 봅시다.

shell sort 1

위 과정을 보면 원소 '5'만을 이동시키면서 1을 인덱스 3에 위치시켰습니다. 기존의 삽입 정렬보다 적게 원소들이 이동했음을 알 수 있습니다.

 

이제 gap이 2일 때 shell sort의 진행 과정을 봅시다.

shell sort 2

처음에 3과 2를 비교하면 2가 3보다 작으므로 3과 2의 위치는 바뀝니다. 그리고 숫자 2를 3보다 2칸 앞에 있는 원소와 비교해야하는데 2칸 앞이라는 위치가 존재하지 않습니다. 따라서 swap은 여기서 끝납니다. 4와 1의 비교도 동일한 경우입니다.

3과 4를 비교할 때는, 4가 3보다 크므로 다른 원소와의 비교 없이 끝납니다.4와 8, 4와 6을 비교할 때도 동일한 경우입니다.

마지막에는 8과 5를 비교합니다. 5는 8보다 작으므로 5와 8의 위치를 바꿉니다. 그리고 5보다 2칸 앞의 원소와 다시 비교합니다. 4는 5보다 작으므로 더 이상의 swap은 발생하지 않습니다.

 

(2022.10.11.화요일 수정)gap이 1이 된 순간은 기존의 삽입 정렬과 동일하게 진행됩니다.

Shell sort 코드(C++)

#include <iostream>
using namespace std;

void shellSort(int[], int);

int main()
{
    int myArray[8] = {3, 8, 6, 5, 4, 4, 2, 1};
    shellSort(myArray, 8);
    return 0;
}

void shellSort(int arr[], int n)
{
    int shrinkRatio = 2;
    int gap = n / shrinkRatio;
    while (gap >= 1)
    {
        for (int i = gap; i < n; i++)
        {
            int value = arr[i];
            int idx = i;
            for (int j = i - gap; j >= 0; j -= gap)
            {
                if (arr[j] > value)
                {
                    arr[j + gap] = arr[j];
                    idx = j;
                }
                else
                {
                    break;
                }
            }
            arr[idx] = value;
        }
        gap /= shrinkRatio;
    }
}

(2022.10.11.화요일 수정)best case에 대해 O(n * log n)만큼 걸리고, worst case에 대해 O(N**2)만큼 소요된다고 합니다.(출처: https://en.wikipedia.org/wiki/Shellsort) 정렬이 진행되는 동안 gap, shrinkRatio, value, i, j 등의 정해진 변수들만 사용하므로 메모리 복잡도는 O(1)이라 할 수 있습니다. shell sort는 주어진 배열 내에서 정렬이 진행되므로 In-place 알고리즘이고, 크기가 같은 원소들의 순서가 보장되지 않으므로 Non-stable한 정렬 알고리즘입니다.