C++로 구현하는 칵테일 정렬(Cocktail Sort) 프로그램

칵테일 정렬(Cocktail Sort)은 버블 정렬(Bubble Sort)의 변형 알고리즘 중 하나로, '양방향 버블 정렬' 또는 '셰이커 정렬(Shaker Sort)'이라고도 불립니다. 일반적인 버블 정렬은 항상 왼쪽에서 오른쪽 방향으로만 탐색하여 첫 번째 패스에서 가장 큰 요소를 배열의 맨 끝으로 보내고, 두 번째 패스에서 두 번째로 큰 요소를 끝에서 두 번째 위치에 배치합니다.

반면 칵테일 정렬은 한 번의 반복 안에서 양방향을 번갈아 가며 순회한다는 점이 특징입니다. 먼저 왼쪽에서 오른쪽으로 스캔하여 가장 큰 값을 뒤로 밀어낸 후, 다시 오른쪽에서 왼쪽으로 스캔하여 가장 작은 값을 앞으로 당겨옵니다. 이러한 양방향 순회 덕분에 배열 끝부분에 있는 작은 값들(소위 '거북이' 요소)이 빠르게 앞쪽으로 이동할 수 있어, 특정 데이터 분포에서는 버블 정렬보다 유리하게 작동합니다.

알고리즘

cocktail(array, n)

Begin
    flag := true
    start := 0, end := n-1
    while flag is set, do
        flag := false
        for i in range start to end-1, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        if flag is not set, then
            break
        end if
        flag := false
        end := end – 1
        for i in range end -1 down to start, do
            if arr[i] > arr[i+1], then
                exchange arr[i] and arr[i+1]
                flag := true
            end if
        done
        start := start + 1
    done
End

C++ 예제 코드

#include<iostream>
using namespace std;

void cocktailSort(int arr[], int n){
    bool flag = true;
    int start = 0, end = n-1;
    while(flag){
        flag = false;
        // 버블 정렬처럼 왼쪽에서 오른쪽으로 스캔
        for(int i = start; i<end; i++){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        // 교환이 하나도 없었다면 이미 정렬된 상태이므로 종료
        if(!flag){
            break;
        }
        flag = false;
        end--; // 끝 포인터를 한 칸 앞으로 이동
        // 오른쪽에서 왼쪽으로 스캔
        for(int i = end - 1; i >= start; i--){
            if(arr[i] > arr[i+1]){
                swap(arr[i], arr[i+1]);
                flag = true;
            }
        }
        start++; // 시작 포인터를 한 칸 뒤로 이동
    }
}

main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    cocktailSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

실행 결과

Sorted Sequence 13 20 32 35 40 54 74 98 98 154

동작 원리 및 성능

위 코드의 핵심 로직을 정리하면 다음과 같습니다.

1. 정방향 스캔: 시작 인덱스(start)부터 끝 인덱스(end)까지 이웃한 두 요소를 비교하여, 앞의 값이 크면 서로 교환합니다. 이 과정에서 가장 큰 값이 자연스럽게 배열의 뒤쪽으로 이동합니다.
2. 역방향 스캔: 끝 포인터(end)를 하나 줄인 뒤, 다시 오른쪽에서 왼쪽으로 스캔하며 교환을 수행합니다. 이때 가장 작은 값이 배열의 앞쪽으로 이동합니다.
3. 범위 축소: 각 반복이 끝날 때마다 start는 증가하고 end는 감소하여, 이미 정렬이 완료된 양 끝 영역은 더 이상 검사하지 않습니다.
4. 조기 종료: 한 패스 동안 단 한 번도 교환이 발생하지 않으면(flag가 false) 배열이 이미 정렬된 것이므로 루프를 즉시 종료합니다.

칵테일 정렬의 시간 복잡도는 최악 및 평균의 경우 O(n²), 이미 정렬된 배열이 입력으로 주어지면 플래그 덕분에 O(n)으로 최적화됩니다. 공간 복잡도는 제자리(in-place) 정렬 방식이므로 O(1)입니다. 학습용으로는 좋지만, 실무에서는 퀵 정렬이나 병합 정렬 같은 O(n log n) 알고리즘을 사용하는 것이 일반적입니다.