Merge Sort, Quick Sort in Python

 

 

면접 단골 질문입니다.

 

"정렬 기법 중에 가장 빠른 정렬기법은 무엇인가요?"

 

누군가는 Quick Sort라고 말할 것이고, 누군가는 Merge Sort라고 말할 것입니다. (혹은 계수 정렬, 기수 정렬이라고 답할지도..?)

 

정렬 기법마다 장단점이 있으며, 최고의 경우와 최악의 경우가 존재합니다.

본 글에서는 O(nlogN) 을 보장하는 가장 대표적이고 자주 사용되는 정렬 기법인 Merge Sort와 Quick Sort 를 Python으로 구현해보고 두 정렬 기법의 장단점을 확인해보도록 하겠습니다.

 

 

 

Merge Sort

---

 

Merge Sort(합병 정렬)은 Divide & Conquer 기법을 사용하여 정렬하는 대표적인 정렬 기법이라고 할 수 있습니다.

 

divide의 merge_sort와 conquer의 merge 함수로 구성됩니다.

 

먼저 merge_sort는 주어진 배열을 왼쪽 절반, 오른쪽 절반으로 나누며 나눈 배열에 대해 merge를 호출합니다.

 

Merge Sort in python

def merge_sort(list):
    # 길이가 1 이하일 경우 배열을 반환
    if len(list) <= 1:
        return list

    # 배열을 왼쪽 절반, 오른쪽 절반으로 나눈다.
    mid = len(list)//2
    left_list = merge_sort(list[:mid])
    right_list = merge_sort(list[mid:])

    # merge 호출
    return merge(left_list, right_list)

 

 

merge 에서는 왼쪽, 오른쪽 배열을 인자로 받아서 정렬해주는데 이 때, result라는 새로운 배열이 필요합니다. 

정렬을 수행하는 방법은

1. 왼쪽, 오른쪽 배열의 0번째 값을 보고 더 작은 값을 result에 넣습니다.

 

2. 더 작은 값이 있던 배열은 맨 앞 요소를 pop하고(여기서는 list slicing으로 처리했습니다.)

 

3. 1과 2를 한쪽 배열이 모두 사라질 때까지 반복합니다.

 

4. result에 left와 right 배열의 남은 요소들을 concat한 값을 반환합니다.

 

 

Merge in python

def merge(left_list, right_list):
    result = []
    left_len = len(left_list)
    right_len = len(right_list)

    #왼쪽, 오른쪽 배열이 존재하는 동안
    while (left_len > 0 and right_len > 0):
        if left_list[0] <= right_list[0]:
            result.append(left_list[0])
            left_list = left_list[1:]
            left_len -= 1
        else:
            result.append(right_list[0])
            right_list = right_list[1:]
            right_len -= 1

    return result + left_list + right_list

 

 

Merge sort는 거의 모든 경우에서 O(nlogN)의 시간복잡도를 보장합니다. 그러나 merge를 실행할 때 N 만큼의 result 배열을 추가적으로 사용해야 하므로 공간복잡도의 관점에서 본다면 다른 정렬기법보다 많은 메모리를 사용하게 됩니다.

 

 

Quick Sort

---

Quick Sort(퀵소트)는 Merge Sort와 마찬가지로 Divide & Conquer 방식을 사용하는 정렬 기법입니다.

Merge Sort와의 가장 큰 차이점은 단순히 절반을 기준으로 왼쪽, 오른쪽 배열로 잘라서 정렬했던 Merge Sort와 다르게

Quick Sort는  Pivotpoint라는 기준점을 설정하여 기준점의 왼쪽, pivot과 같은 값을 담을 배열, 오른쪽 배열로 나누어 정렬한다는 것입니다.

 

pivot의 왼쪽 배열은 pivot보다 작은 값

pivot의 오른쪽 배열은 pivot보다 큰 값

pivot의 중간 배열은 pivot과 같은 값

 

으로 구성됩니다.

 

Merge Sort와 마찬가지로 배열의 길이가 1 이하가 되는것을 기저조건으로 설정하고 left, middle, right 배열로 나누어 quick_sort를 재귀호출하게 됩니다.

 

 

Quick Sort in python 

def quick_sort(list):
    # 길이가 1 이하일 경우 배열을 반환
    if len(list) <= 1:
        return list

    # 배열을 왼쪽, pivot, 오른쪽으로 나누어 재귀호출한다.
    # 왼쪽 : pivot보다 작은 값
    # pivot : pivot과 같은 값
    # 오른쪽 : pivot보다 큰 값
    pivotpoint = list[len(list)//2]
    left, pivot, right = [], [], []
    for i in list:
        if i < pivotpoint:
            left.append(i)
        elif i > pivotpoint:
            right.append(i)
        else:
            pivot.append(i)
    return quick_sort(left) + pivot + quick_sort(right)

 

 

정리

---

 

 

https://www.interviewkickstart.com/learn/merge-sort-vs-quicksort-performance-analysis

Merge Sort vs. Quicksort: Algorithm Performance Analysis

 

위의 링크에서 Quick Sort와 Merge Sort의 성능을 비교한 지표를 볼 수 있습니다.

 

Quick Sort가 Merge Sort에 비해 근소한 차이로 성능이 좋다는 것을 알 수 있습니다.

그러나 이미 정렬되어있는 경우 Quick Sort는 O(N^2)으로 끔찍한 성능을 보여줍니다.

 

 

결론 3줄 요약

 

1. 대부분의 경우에서 Quick Sort가 Merge Sort보다 근소하게 빠르다(성능이 좋다.) 그러나 최악의 경우 Quick Sort는 O(N^2)이다. Merge Sort는 O(nlogN)을 보장

 

2. Merge Sort는 메모리를 추가로 사용하기 때문에 공간복잡도적인 측면에서 비효율적이다

 

3. 정렬해야하는 수의 최댓값이 작다면 O(N)인 Counting Sort를 사용하자(?) 어떤 정렬 알고리즘이 무조건 좋다고 할 수 없다. 상황에 맞게 적절한 정렬 기법을 사용하는 것이 중요하다