칵테일 셰이커 정렬🧺

소개

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

 

정렬 과정

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

 

+-----+-----+-----+-----+-----+
|  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  |
+-----+-----+-----+-----+-----+

 

알고리즘 분석

비교 횟수

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

 

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

 

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

 

$$
(n - 1) + (n - 2) + ... + 2 + 1 = (n - 1) * n / 2 = \frac{n(n-1)}{2}
$$

 

자리 교환 횟수

최선의 경우(이미 정렬된 원소들이 주어지는 경우), 자리 교환이 이루어지지 않기 때문에 시간 복잡도에 영향이 없다. 그러나 최악의 경우(역순 정렬된 원소들이 주어지는 경우), 모든 검사에서 자리 교환이 이루어진다. 따라서 평균적으로 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(n^2)이라는 점과 많은 수학자들이 거품 정렬을 개선하기 위해 얼마나 많은 노력을 했는지만 알고 넘어가도 좋을 것 같다.