정렬 알고리즘2: 퀵, 병합

참고

• 「취업을 위한 코딩 테스트이다 with 파이썬」 나동빈 지음
• 「Do it! 자료구조와 함께 배우는 알고리즘 입문 파이썬 편」 시바타 보요 지음
• https://yabmoons.tistory.com/250

 

콘텐츠

1. 개념
2. 파이썬 구현 코드
3. 시간 복잡도
4. 장단점

• 퀵 정렬과 병합 정렬 선택 기준

---

대부분의 프로그래밍 언어에서 정렬 라이브러리는 속도가 빠른 퀵이나 병합 정렬을 기반으로 한다.

 

퀵 정렬 (Quick Sort)

• 개념

파트1

피벗pivot이라는 기준에 의해 리스트 내 큰 숫자와 작은 숫자를 교환한다. 피벗을 설정하는 기준은 다양하지만, 리스트의 첫 번째 원소를 피벗으로 설정하는 "호어 분할 방식"이 가장 대표적이다.

초록색이 피벗이고, 노란색 화살표는 5 다음 숫자에서부터 피벗보다 큰 값을 찾고, 파란색 화살표는 리스트 끝에서부터 피벗보다 작은 값을 찾는다. 각 숫자에 도달하면 두 화살표가 가리키는 숫자를 교환한 후 계속 탐색한다. 그러다가 두 화살표가 엇갈리면, 피벗과 더 작은 값을 가리키는 화살표끼리 교환한다. 그럼 피벗은 해당 위치에 정렬된다.

 

• 파이썬 구현 코드

def quick(data, start, end):
    if start >= end:
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right:
        while left <= end and data[left] <= data[pivot]:
            left += 1

        while right > start and data[right] >= data[pivot]:
            right -= 1

        if left > right:
            data[pivot], data[right] = data[right], data[pivot]
        else:
            data[left], data[right] = data[right], data[left]

    quick(data, start, right - 1)
    quick(data, right + 1, end)

 

• 시간 복잡도

피벗에 따라 시간 복잡도가 달라진다. 평균 시간 복잡도는 O(n log n)이다. 분할 과정에서 log n 시간이 걸리고, 각 분할 과정에서마다 n개의 데이터를 비교하기 때문이다.

그러나 이미 리스트가 정렬되어 있는 최악의 경우에는 O(n²) 시간 복잡도를 갖는다. 왜냐하면 1, 2, 3, 4가 있을 때 1과 2, 3, 4 / 2와 3, 4 / 3과  4처럼 계속 원소 1개와 나머지로 나뉘기 때문에 n번의 분할이 발생하기 때문이다.

 

한편 C++을 비롯한 많은 프로그래밍 언어의 정렬 라이브러리가 퀵 정렬을 기반으로 하는데, 이곳에는 최악의 경우에도 O(n log n)을 보장하기 위해 피벗 설정 시 추가적인 작업을 거친다.

 

• 장단점

1. 속도가 빠르다. 똑같은 O(n log n) 시간 복잡도를 가진 다른 정렬 알고리즘보다도 속도가 빠른 편이다.

 

1. 피벗 설정 방식에 따라 시간 복잡도가 O(n)이 될 수도 있다.

 

 

 

 

병합 정렬 (합병 정렬, Merge Sort)

• 개념

분할과 정복 기법이 적용된 정렬 방법이다. 리스트 내 n개의 데이터를 n / 2로 두 리스트로 나누고, 이들을 각각 정렬한 뒤 병합한다.

위 그림에서 파란색 화살표가 한 리스트를 두 개의 리스트로 나누는 '분할'이고, 각 리스트를 정렬하는 것은 '정복', 초록색 화살표는 두 리스트를 하나로 합치는 '병합/합병' 작업이다.

 

• 파이썬 구현 코드

def merge_sort(array):
    if len(array) < 2:
        return array
    
    mid = len(array) // 2

    left = merge_sort(array[:mid])
    right = merge_sort(array[mid:])
    return merge(left, right)


def merge(left, right):
    result = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            result.append(left[l])
            l += 1
        else:
            result.append(right[r])
            r += 1

    result += left[l:]
    result += right[r:]
    return result

 

• 시간 복잡도

리스트를 정렬하는 과정은 리스트를 계속 반으로 쪼개어 나가기 때문에 O(log n) 시간 복잡도를 갖는다. 정렬된 두 리스트를 병합하는 과정의 시간 복잡도는 left 리스트의 원소 개수 l, right 리스트의 원소 개수 r의 합인 O(l + r)이다. 그러나 합병되는 두 리스트는 결국 최종적으로 기존 n개의 데이터를 가진 리스트이므로, 시간 복잡도 역시 O(n)이다. 따라서 병합 정렬의 최종 시간 복잡도는 O(n log n)이다.

 

• 장단점

1. 똑같은 시간 복잡도를 가진 퀵 정렬은 피벗에 따라 속도가 저하될 수 있지만, 병합 정렬은 늘 빠른 속도로 정렬한다.

 

1. 병합 과정에서 result라는 임시 리스트를 사용한 것처럼 추가적인 메모리 할당이 필요하다.

 

---

퀵 정렬과 병합 정렬 선택 기준

퀵 정렬은 제자리 정렬로 추가적인 메모리 사용이 없지만, 피벗을 어떻게 설정하는가에 따라 성능 편차가 발생한다.

병합 정렬은 정렬된 값을 담는 임시 리스트 때문에 추가적인 메모리가 사용되지만, 늘 O(n log n) 시간 복잡도를 보장한다.

 

따라서 언제, 무슨 정렬 방법을 사용하는 기준은 "메모리 추가 사용 가능 여부"와 "데이터의 상태"이다.

 

예를 들어 데이터가 정렬된 최악의 상황에서는 퀵 정렬은 O(n²), 병합 정렬은 O(n log n)이므로 병합 정렬을 사용하는 것이 옳다. 즉, 일반적으론 병합 정렬을 선택하는 것이 최선의 선택일 것이다.

 

그러나 만약 추가적인 데이터 할당이 불가능한 상황이라면, in-place 정렬인 퀵 정렬을 사용할 수밖에 없다.