온갖 정렬 02

강한친구·2021년 9월 14일

들어가기전에

이전글에서는 정렬을 다루면서 기본적인 삽입, 선택, 버블 3가지만 다뤄보았다.

이 3가지 정렬들의 공통점이 있다면 코드로 구현하는것이 비교적 쉽지만, 시간복잡도면에서 오늘 소개할 Merge, Quick에 비해 많이 밀린다는 점이다.

병합정렬 MergeSorting

Merge Sorting은 Divide & Conquer 기법을 이용한 방식이라 할 수 있다. 리스트를 반으로 나누면서 더 이상 나눌 수 없을때까지 계속 쪼갠다. 그 후, 각 값을 비교하면서 더 작은값을 큰 값의 앞에 배치하는식으로 정렬을 하면된다.

즉 리스트를 나누는 Divide, 정렬을 하는 Conquer 그리고 마지막으로 합치는 Combine으로 이루어진 분할정복 기법이라 할 수 있는것이다.
우선 분할하는 부분의 코드를 알아보겠다

def merge_sort(n):
    if len(n) <= 1:
        return n
    middle = len(n) // 2
    left_list = n[:middle]
    right_list = n[middle:]

    left_list = merge_sort(left_list)
    right_list = merge_sort(right_list)
    return list(merge(left_list, right_list))

리스트의 길이의 절반을 middle로 설정하고, 슬라이싱을 통해 리스트를 반으로 나눠준다. 이 과정을 재귀함수 형태로 반복하며, 리스트의 분할이 끝나면 그 때부터는 merge_sort라는 새로운 함수를 호출하여 정렬을 시작하게 된다.

def merge(left, right):
    res = []
    while len(left) != 0 and len(right) != 0:
        if left[0] > right[0]:
            res.append(right[0])
            right.remove(right[0])
        else:
            res.append(left[0])
            left.remove(left[0])
    if len(left) == 0:
        res = res + right
    else:
        res = res + left
    return res

입력받은 list를 크기에 맞춰서 정렬하는 기능을 수행하는 함수이다. 좌, 우 리스트 어느 한쪽의 크기가 0이 되기 전까지 수행하는 while문을 작성한 후, left 값과 right 값을 비교하며 더 작은값을 먼저 두고 해당 리스트에서는 삭제하는 방식으로 진행한다.
그 후 어느 한쪽 리스트가 0이 되었다면 남은 리스트를 전부 결과 res 뒤에 붙여준 뒤, 반환하면 된다.

분할정복을 이용한 MergeSorting의 시간복잡도는 얼핏보면 전체 리스트를 다 나누고 다 시합치니깐 O(n)이 아닌가 하는 의구심을 품을 수 있다.
하지만 실제로 MergeSorting의 시간복잡도는 O(n log(n)) 이다.

병합정렬의 시간복잡도

분할과정
- 길이 n의 리스트를 반으로 나누면 n/2 리스트가 2개가 생성된다. 만약 길이가 8인 리스트를 나눈다고 하면
  [8 -> 4, 4 -> 2, 2, 2, 2 -> 1, 1, 1, 1, 1, 1, 1, 1]
  총 3회만에 다 나눠졌다는것을 알 수 있다.
  즉, 분할과정은 밑이 2인 log의 n 즉, O(log(n))임을 알 수 있다.
병합과정
- 이를 병합하는 과정은 각 리스트별로 하기때문에 n이다.
최종적인 시간복잡도는 O(n log(n))이라 할 수 있다.

퀵 정렬 QuickSorting

퀵 정렬은 Pivot값을 설정하고 그 값을 기준으로 정렬을 하는 방식이다.

pivot값은 보통 첫번째 값, 혹은 마지막 값으로 잡으나, 실제로는 중앙값 혹은 리스트안의 랜덤값등 다양하게 잡을 수 있다.

pivot을 정하고 나면 그 후 리스트를 두개 생성하여 pivot 보다 큰 수와 작은 수를 나눠서 저장한다. 이 과정을 계속 반복하여 리스트를 정렬하는 방식이다.
이처럼 병합정렬과 유사한 Divide & Conquer 방식으로 정렬을 수행하게 된다.

def quick_sort(n):
    if len(n) <= 1:
        return n
    else:
        pivot = n.pop() # pivot is the last one
    bigger = []
    smaller = []
    for i in range(len(n)):
        if n[i] > pivot:
            bigger.append(n[i])
        else:
            smaller.append(n[i])
    return quick_sort(smaller) + [pivot] + quick_sort(bigger)

퀵정렬의 시간복잡도

분할과정
- 길이 n의 리스트를 반으로 나누면 n/2 리스트가 2개가 생성된다. 만약 길이가 8인 리스트를 나눈다고 하면
  [8 -> 4, 4 -> 2, 2, 2, 2 -> 1, 1, 1, 1, 1, 1, 1, 1]
  총 3회만에 다 나눠졌다는것을 알 수 있다.
  즉, 분할과정은 밑이 2인 log의 n 즉, O(log(n))임을 알 수 있다.
병합과정
- 이를 병합하는 과정은 각 리스트별로 하기때문에 n이다.
최종적인 시간복잡도는 O(n log(n))이라 할 수 있다.