칵테일 쉐이커 정렬(Cocktail Shaker Sort)

본 글은 버블 정렬에 대해 알고 있다는 가정 하에 작성되었습니다. 버블 정렬을 모르시는 분들은 제가 전에 썼던 글을 보고 오시면 더 편하게 이해하실 수 있습니다.

2022.09.05 - [알고리즘] - 버블 정렬(Bubble sort)

버블 정렬할 때 생기는 문제점

버블 정렬을 할 때 길이가 5인 정수형 배열({5, 4, 3, 2, 1})을 정렬한다고 생각합시다. 5는 1번의 pass로 제 위치로 갈 수 있지만 1은 마지막 pass까지 진행해야 제 위치로 갑니다. 이렇듯 정수형 배열을 정렬할 때 값들이 임의로 섞여있는 경우 큰 값들은 적은 pass를 통해 정렬되지만 작은 값들은 거의 마지막 pass까지 진행해야 합니다.

bubble sort 결과

여기서 크기가 작은 값들을 빠르게 제 위치로 이동시킬 수 있는 칵테일 셰이커 정렬(Cocktail Shaker Sort)이 등장합니다.

 

칵테일 쉐이커 정렬(Cocktail Shaker Sort)

바텐더가 셰이커를 들고 흔드는 모습을 상상해보세요. 칵테일 쉐이커 정렬은 쉐이커가 흔들리는 것과 같이 정렬이 진행됩니다.

칵테일 쉐이커 정렬은 기본적으로 버블 정렬 방식을 따릅니다. 여기서 핵심은 pass에 따라 버블 정렬이 진행되는 방향이 전환되는 것입니다. 예를 들어 1, 3, 5번째 pass는 큰 값을 오른쪽으로 보내는 방식, 2, 4, 6번째 pass는 작은 값을 왼쪽으로 보내는 방식으로 진행시킬 수 있습니다. 또는 이 반대로 진행할 수도 있습니다. 위의 배열을 가지고 칵테일 쉐이커 정렬을 2번의 pass까지만 진행해보겠습니다.

1번째 pass

cocktail shaker sorting pass 1

첫 번째 pass에서는 큰 값을 오른쪽으로 보내는 방법으로 진행했습니다. 방법은 bubble sort와 동일합니다.

두 번째 pass

cocktail shaker sorting pass 2

두 번째 pass는 작은 값을 왼쪽으로 보내는 방법으로 진행했습니다. 정렬된 맨 끝 값부터가 아니라 그 전의 값부터 인접한 두 값 간의 비교로 정렬이 이루어집니다. 두 번째 pass를 통해 기존 bubble sort보다 1의 값이 빠르게 제 자리를 찾았음을 볼 수 있습니다.

Pass 3을 Pass 1처럼, Pass 4를 Pass 2처럼 진행하면 정렬된 배열을 얻을 수 있습니다.

칵테일 셰이커 정렬 코드(C++)

위에서 설명한 칵테일 쉐이커 정렬에 추가적으로 개선 사항들을 적용시킬 수도 있습니다. 개선할 만한 사항들은 전에 적은 버블 정렬 글에서 적은 사항들과 동일합니다. 따라서 모두 적용한 칵테일 쉐이커 정렬 코드는 아래와 같습니다.

#include <iostream>
using namespace std;

void cocktail_sort(int arr[], int n)
{
    int last_forward_swapped = n;
    int last_backward_swapped = 0;
    for (int pass = 1; pass < n; pass++)
    {
        bool swapped = false;
        if (pass % 2 != 0)
        {
            int forward_swapped = 0;
            for (int i = last_backward_swapped; i < last_forward_swapped - 1; i++)
            {
                if (arr[i] > arr[i + 1])
                {
                    swap(arr[i], arr[i + 1]);
                    forward_swapped = i + 1;
                    swapped = true;
                }
            }
            last_forward_swapped = forward_swapped;
        }
        else
        {
            int backward_swapped = n;
            for (int i = last_forward_swapped; i > last_backward_swapped; i--)
            {
                if (arr[i - 1] > arr[i])
                {
                    swap(arr[i - 1], arr[i]);
                    backward_swapped = i - 1;
                    swapped = true;
                }
            }
            last_backward_swapped = backward_swapped;
        }

        if (!swapped)
        {
            break;
        }
    }
}

int main()
{
    int my_arr[10] = {0, 1, 5, 3, 4, 2, 6, 7, 8, 9};
    cocktail_sort(my_arr, 10);
    printf("Result: ");
    for (int idx = 0; idx < 10; idx++)
    {
        printf("%d ", my_arr[idx]);
    }
    cout << "\n";
    return 0;
}

코드를 보면 아실 수 있듯이 칵테일 쉐이커 정렬은 버블 정렬과 동일하게 best case에 대해서는 O(n), worst case에 대해서는 O(n**2), In-place 알고리즘이면서 stable 한 정렬 알고리즘임을 알 수 있습니다.