홀짝 정렬 (Odd-Even Sort)

1. Introduction

홀짝 정렬은 홀수부분과 짝수부분을 나눠서 정렬하는 버블 정렬의 variation이다. 칵테일 정렬과 같이 시간복잡도가 $O(n^2)$에 머물러 있지만 오리지널 버블 정렬보다 빠른 것으로 알려져 있다.

 

2. Approach

다음 이미지는 홀짝 정렬의 과정을 시각적으로 보여준다. 출처는 위키피디아.

Example of Odd-Even Sort

다음 코드는 파이썬으로 구현된 홀짝 정렬이다.

def odd_even(arr, a, b): 
    isSorted = True
    
    while isSorted == True: 
        isSorted = False
        for i in range (a, b, 2): 
            if arr[i] > arr[i + 1]: 
                arr[i], arr[i + 1]= arr[i + 1], arr[i] 
                isSorted = True
  
        for i in range(a+1, b, 2): 
            if arr[i] > arr[i + 1]: 
                arr[i], arr[i + 1] = arr[i + 1], arr[i] 
                isSorted = True

 

3. Discussion

홀짝 정렬은 버블정렬의 루틴을 2개씩 건너 뛰어가면서 정렬하는 방법인데 이를 더 확장해서 3부분, 4부분, ... n부분까지 나눠서 정렬할 수 있다.

버블 정렬의 variation이므로 당연히 stable한 정렬이며 추가적인 공간을 요구하지 않는다.