칵테일 정렬 (Cocktail Sort)

1. Introduction

칵테일 정렬 (또는 칵테일-셰이커 정렬)은 버블 정렬의 Variation으로, 한번의 루틴마다 방향을 바꿔서 정렬하는 알고리즘이다. 버블 정렬에서 크게 바뀌지는 않았지만 일반적인 경우에서 버블 정렬보다 빠르다고 한다.

2. Approach

다음 이미지는 칵테일 정렬의 과정을 시각화한 것이다. 출처는 위키피디아. 양 끝을 왔다갔다 하면서 비교하는 인덱스가 배열의 중간으로 수렴하는 것을 볼 수 있다.

Example of Cocktail Sort

다음 코드는 칵테일 정렬의 파이썬 구현이다.

def cocktail(arr, a, b): 
    swapped = True
    
    while swapped == True: 
        swapped = False
        for i in range (a, b): 
            if arr[i] > arr[i + 1]: 
                arr[i], arr[i + 1]= arr[i + 1], arr[i] 
                swapped = True
  
        if swapped == False: 
            break
  
        swapped = False
  
        b = b-1
  
        for i in range(b-1, a-1, -1): 
            if arr[i] > arr[i + 1]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
                swapped = True
  
        a = a + 1

3. Discussion

움직이는 방식만 바꿨기 때문에 시간복잡도 ($O(n^2)$)의 개선은 없다. 그러나 버블 정렬에 비해 빠르게 작동한다고 한다. 이렇게 한쪽 끝에서 다른 쪽으로 이동하는 방식으로 처리하는 방법은 나중에 디스크 스케쥴링에서도 사용된다. SCAN 알고리즘이라고 하는데 그 쪽에서 자세히 다루도록 하겠다.