칵테일 정렬(Cocktail Sort)은 버블 정렬(Bubble Sort)의 변형으로, 안정성(stable)을 보장하는 비교 기반 정렬 알고리즘입니다. 양방향 버블 정렬(Bidirectional Bubble Sort), 칵테일 셰이커 정렬(Cocktail Shaker Sort), 셰이커 정렬(Shaker Sort), 리플 정렬(Ripple Sort), 셔플 정렬(Shuffle Sort), 셔틀 정렬(Shuttle Sort) 등 다양한 이름으로도 알려져 있습니다.
일반적인 버블 정렬이 매번 한 방향(앞에서 뒤로)만 탐색하는 것과 달리, 칵테일 정렬은 리스트를 순회할 때마다 앞뒤 양방향으로 번갈아 가며 정렬한다는 점이 특징입니다. 이러한 방식 덕분에 배열 끝쪽에 있는 작은 값(소위 '거북이' 요소)을 더 빠르게 앞으로 이동시킬 수 있습니다.
입력: 5 3 4 2 1 출력: 1 2 3 4 5
동작 원리
칵테일 정렬에서 배열은 아직 정렬되지 않은 요소들로 구성됩니다. 알고리즘은 각 패스(pass)마다 두 방향 모두에서 작업을 수행합니다.
구체적으로는 다음과 같은 과정을 반복합니다.
1. 정방향 패스: 배열의 처음부터 끝까지 이동하면서 인접한 두 요소를 비교하고, 순서가 잘못되어 있으면 서로 교환(swap)합니다. 이 단계가 끝나면 가장 큰 값이 배열의 맨 뒤로 이동합니다.
2. 역방향 패스: 배열의 끝에서 시작 부분으로 이동하면서 같은 방식으로 인접 요소를 비교하고 교환합니다. 이 단계가 끝나면 가장 작은 값이 배열의 맨 앞으로 이동합니다.
3. 더 이상 교환이 발생하지 않거나, 정렬해야 할 범위가 없어질 때까지 위 과정을 반복합니다.
C++ 예제 코드
#include <iostream>
using namespace std;
int main() {
int arr[] = { 5, 3, 4, 2, 1 };
int m = 5;
int n, c;
n = m;
do {
// 정방향 패스: 큰 값을 뒤로 이동
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
arr[i] = arr[i] + arr[i + 1];
arr[i + 1] = arr[i] - arr[i + 1];
arr[i] = arr[i] - arr[i + 1];
}
}
n = n - 1;
// 역방향 패스: 작은 값을 앞으로 이동
for (int i = m - 1, c = 0; i >= c; i--) {
if (arr[i] < arr[i - 1]) {
arr[i] = arr[i] + arr[i - 1];
arr[i - 1] = arr[i] - arr[i - 1];
arr[i] = arr[i] - arr[i - 1];
}
}
c = c + 1;
}
while (n != 0 && c != 0);
// 정렬 결과 출력
for (int i = 0; i < m; i++) {
cout << arr[i] << "\t";
}
}실행 결과
1 2 3 4 5
시간 복잡도
칵테일 정렬의 시간 복잡도는 다음과 같습니다.
- 최악의 경우 및 평균: O(n²)
- 최선의 경우(이미 정렬된 배열): O(n)
- 공간 복잡도: O(1) — 제자리(in-place) 정렬
- 안정성: 동일한 값의 상대적 순서가 유지되는 안정 정렬
이처럼 칵테일 정렬은 버블 정렬과 시간 복잡도는 같지만, 양방향으로 순회함으로써 특정 입력 패턴에서는 더 적은 패스로 정렬을 완료할 수 있는 장점이 있습니다.