칵테일 정렬(Cocktail Sort)은 버블 정렬(Bubble Sort)의 변형 알고리즘으로, '양방향 버블 정렬' 또는 '셰이커 정렬(Shaker Sort)'이라고도 불립니다. 일반적인 버블 정렬이 요소를 한 방향(왼쪽에서 오른쪽)으로만 순회하며 가장 큰 값을 배열 끝으로 밀어내는 것과 달리, 칵테일 정렬은 양방향(왼쪽→오른쪽, 오른쪽→왼쪽)을 번갈아가며 순회한다는 점이 특징입니다.
칵테일 정렬 자바 예제 코드
다음은 자바로 작성한 칵테일 정렬 프로그램입니다.
public class Demo{
static int temp;
static void Cocktail(int a[], int n){
boolean swap = true;
int begin = 0,i;
int end = n - 1;
while (swap) {
swap = false;
for (i = begin; i < end; ++i){
if (a[i] > a[i + 1]){
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = true;
}
}
if (!swap)
break;
swap = false;
for (i = end - 1; i >= begin; --i){
if (a[i] > a[i + 1]){
temp = a[i];
a[i]=a[i+1];
a[i+1]=temp;
swap = true;
}
}
++begin;
}
}
public static void main(String[] args) {
int my_arr[] = {34, 78, 90, 32, 67, 12, 1, 0, 95};
Cocktail(my_arr, my_arr.length);
System.out.println("The sorted array is ");
for (int i = 0; i < my_arr.length; i++)
System.out.print(my_arr[i]+" ");
System.out.println();
}
}실행 결과
The sorted array is 0 1 12 32 34 67 78 90 95
칵테일 정렬의 동작 원리
1단계: 왼쪽 → 오른쪽 순회
첫 번째 단계에서는 버블 정렬과 마찬가지로 루프가 왼쪽에서 오른쪽으로 진행되며 인접한 두 요소를 비교합니다. 왼쪽 값이 오른쪽 값보다 크면 두 값을 서로 교환(swap)합니다. 첫 번째 순회가 끝나면 가장 큰 요소가 배열의 맨 끝에 위치하게 됩니다.
2단계: 오른쪽 → 왼쪽 순회
다음 단계에서는 방금 정렬된 마지막 요소를 제외하고 루프가 오른쪽에서 왼쪽으로 진행됩니다. 이 과정에서도 인접한 요소들을 비교하며, 더 큰 요소를 배열의 끝 쪽으로 이동시킵니다.
3단계: 반복 및 종료 조건
이러한 양방향 순회를 한 번 수행할 때마다 정렬 범위의 시작점(begin)이 하나씩 증가하여 이미 정렬된 영역은 다시 검사하지 않습니다. 더 이상 교환이 발생하지 않으면(swap == false) 알고리즘은 종료됩니다.
칵테일 정렬의 장점과 성능
- 거북이 문제(Turtle Problem) 개선: 배열 뒤쪽에 있는 작은 값이 앞쪽으로 빠르게 이동할 수 있어, 일반 버블 정렬보다 불규칙한 데이터에서 유리합니다.
- 시간 복잡도: 최악의 경우 O(n²), 평균 O(n²)이며, 이미 정렬된 배열의 경우 한 번의 순회만으로 종료되므로 최선의 경우 O(n)입니다.
- 공간 복잡도: 제자리(in-place) 정렬 방식으로 추가 메모리가 거의 필요하지 않습니다(O(1)).
칵테일 정렬은 구현이 간단하면서도 버블 정렬의 비효율을 일부 보완한 알고리즘으로, 정렬 알고리즘의 기본 원리를 학습하기에 좋은 예제입니다.