칵테일 셰이커 정렬

소개

칵테일 셰이커 정렬(Cocktail shaker sort)는 거품 정렬에서 파생된 정렬 알고리즘입니다. 양방향 거품 정렬 혹은 셰이커 정렬 등으로 불립니다. 시간 복잡도가 O(n2)O(n^2) 으로 거품 정렬과 비슷합니다. 정렬하는 게 마치 칵테일을 위아래로 흔드는 모습과 비슷하다 하여 이런 이름이 붙었습니다.

정렬 과정

다음과 같이 다섯 개의 정수가 주어졌을 때, 오름 차순으로 정렬해보겠습니다.

+-----+-----+-----+-----+-----+
| 5 | 4 | 1 | 3 | 2 |
+-----+-----+-----+-----+-----+

거품 정렬처럼 인덱스 0의 값과 인덱스 1의 값을 비교하는걸 시작으로 인덱스 3의 값과 인덱스 4의 값까지 비교합니다.

+-----+-----+-----+-----+-----+
| 4 | 5 | 1 | 3 | 2 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 4 | 1 | 5 | 3 | 2 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 4 | 1 | 3 | 5 | 2 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 4 | 1 | 3 | 2 | 5 |
+-----+-----+-----+-----+-----+

이 부분까지는 거품 정렬과 동일합니다. 그러나 다음 단계부터 차이를 보입니다.

거품 정렬에서는 다시 인덱스 0의 값과 인덱스 1의 값을 비교하지만, 칵테일 셰이커 정렬에서는 역순으로 인덱스 2의 값과 인덱스 3의 값을 비교합니다.

이번에는 역순으로 정렬을 시작합니다.

+-----+-----+-----+-----+-----+
| 4 | 1 | 2 | 3 | 5 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 4 | 1 | 2 | 3 | 5 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 4 | 2 | 3 | 5 |
+-----+-----+-----+-----+-----+

다시 인덱스 0의 값과 인덱스 1의 값 비교를 마쳤으면, 처음처럼 다시 인덱스가 증가하는 쪽으로 이동하며 정렬합니다.

여기서 주의해야할 점은 처음에 오른쪽으로 이동하면서 검사했을 때 가장 큰 값이 우측으로 이동했기 때문에 다음 검사부터는 한 칸 전까지만(인덱스 3) 검사하면 됩니다. 반대로 왼쪽으로 이동하면서 검사했을 때 가장 작은 값이 좌측으로 이동했기 때문에 다음 검사부터는 한 칸 다음까지만(인덱스 1) 검사하면 됩니다.

이렇게 한 줄 순회가 끝나면 검사 구역을 한 칸씩 당겨서 정렬이 완료된 곳을 다시 검사하는 일이 없도록 합니다. 결국, 앞 뒤가 한 칸 씩 줄어들다가 마지막에는 원소들의 가운데를 검사하고 정렬이 완료됩니다.

이어진 정렬을 계속 보겠습니다.

+-----+-----+-----+-----+-----+
| 1 | 2 | 4 | 3 | 5 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+
+-----+-----+-----+-----+-----+
| 1 | 2 | 3 | 4 | 5 |
+-----+-----+-----+-----+-----+

알고리즘 분석

비교 횟수

칵테일 셰이커 정렬은 거품 정렬과 마찬가지로 한 번의 검사마다 비교 대상이 하나씩 줄어듭니다. 전체 원소의 개수가 nn 개면, 총 (n1)(n - 1) 번 검사하면 한 번 정렬이 완료됩니다.

앞 선 예제에서 총 원소가 5개 이므로, 4+3+2+1=104 + 3 + 2 + 1 = 10 번 검사하면 전체 정렬이 완료됩니다. 이는 거품 정렬과 순회 방향의 차이만 있을 뿐입니다.

이를 수식으로 일반화하면 다음과 같습니다.

(n1)+(n2)+...+2+1=(n1)n/2=n(n1)/2(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = n(n - 1) / 2

자리 교환 횟수

최선의 경우(이미 정렬된 원소들이 주어지는 경우), 자리 교환이 이루어지지 않기 때문에 시간 복잡도에 영향이 없습니다. 그러나 최악의 경우(역순 정렬된 원소들이 주어지는 경우), 모든 검사에서 자리 교환이 이루어집니다. 따라서 평균적으로 O(n2)O(n^2) 의 시간 복잡도를 가집니다.

구현

앞 선 예제를 코드로 구현하면 다음과 같습니다.

void cocktail_shaker_sort(int *array) {
int left = 0, right = SIZE - 1, temp;
while (1) {
for (int i = left; i < right; i++) {
if (array[i] > array[i + 1]) {
temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
if (left + 1 == right)
return;
}
right--;
for (int i = right; i > left; i--) {
if (array[i - 1] > array[i]) {
temp = array[i - 1];
array[i - 1] = array[i];
array[i] = temp;
}
if (left + 1 == right)
return;
}
left++;
}
}

정리

칵테일 셰이커 정렬은 거품 정렬과 비슷한 방식으로 동작하지만 특정한 입력 데이터에 따라 속도가 조금 더 빠를 수 있다고 합니다. 다만, 특정한 입력 데이터에 관한 내용은 아무리 찾아봐도 나오지 않았습니다.

생각해볼 수 있는 한 가지는 굉장히 긴 배열 데이터가 입력됐을 때 마지막 인덱스 탐색을 마친 후에 다시 처음 인덱스로 돌아가는 시간이 없어진다는 차이가 아닐까 싶습니다.

두 정렬 모두 평균 시간 복잡도가 O(n2)O(n^2) 이라는 점과 많은 수학자들이 거품 정렬을 개선하기 위해 얼마나 많은 노력을 했는지만 알고 넘어가도 좋을 것 같습니다.