[알고리즘] 분할 정복(Divide & Conquer)과 퀵, 병합 정렬(Quick & Merge Sort)

Posted on | In
프로그래밍과 코드 분석 강화. 알고리즘을 활용한 프로그래밍. 분할 정복 기반 퀵 정렬, 병합 정렬

분할 정복(Divide & Conquer)

분할정복

  • 복잡하거나 큰 문제를 여러개로 나눠서 푸는 방법이다.
    • 병렬적으로 문제를 해결할 수 있다.
      (하지만, 문제를 해결하기 위해 문제해결 함수가 재귀적으로 호출될 수 있으므로 메모리의 추가사용이 있을 수 있다.)
  • 재귀호출과 분할정복의 차이
    • 재귀호출: 같은 함수코드를 재호출하는 것
    • 분할정복: 비슷한 작업을 재진행하는 것
  • 비슷한 크기로 문제를 분할하고, 해결된 문제를 제외하고 동일한 크기로 문제를 다시 분할한다.

과정

  1. 본 문제를 서브문제로 분할한다.(divide)
  2. 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합한다.(Merge)
  3. 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구한다.(base case, 기본 케이스)

조건

  1. 본 문제를 서브문제로 분할할 수 있는가?(Divide)
  2. 서브문제의 답을 병합(또는 조합)하여 본 문제의 답을 구하는 것이 효율적인가?(Merge, Conquer)
1
2
3
4
5
6
7
8
9
# 재귀 : 1부터 10까지의 합

def func(num):
  if num < 1:
    return 0
  else:
    return num + func(num-1)

func(10)

1
2
3
4
5
6
7
8
9
10
11
# 분할정복 : 1부터 10까지의 합

def func(num):
  if num == 1:
      return 1
  if num % 2 == 1:
      return func(num - 1) + num
  else:
      return func(num / 2) * 2 + (num / 2) * (num / 2) 

func(10)

퀵 정렬과 병합 정렬(Quick & Merge Sort)

  • 일반적으로 퀵 정렬의 시간 복잡도가 병합 정렬보다 크다.
    (둘 다 O(NlogN)정도의 시간 복잡도를 갖는다)
    • 병합 정렬은 분할 정복 로직으로 인해, 전체 데이터를 기준으로 처음과 끝을 계속해서 탐색하기 때문에 퀵 정렬에 비해 느리다.
    • 퀵 정렬은 처음에 전체 탐색을 할 때 좌우로 나눠서 재귀적으로 수행하기 때문에 병합 정렬보다 빠르다.
  • 퀵 정렬은 한정적인 범위에서 데이터를 정렬하기 때문에 캐시를 덜 활용하고, 하드웨어적으로 효율적이다.
    • 퀵 정렬도 분할정복을 통해 정렬하고, 피벗이라는 별도의 노드를 지정해두고 재귀적으로 수행하기 때문에 더 빠르다.
  • 병합 정렬이 활용되는 이유는 퀵 정렬보다 빠르지 않지만, 안정(stable) 정렬이기 때문에 데이터가 중복되었더라도 영향을 덜 받는다.
    • 하지만 퀵 정렬은 성능이 우수함에도 성능편차가 크고, 피벗설정 등 다루기 어려운 점이 존재해서 실무에서 활용되기 어렵다.

퀵 정렬(Quick Sort)

  • 퀵 정렬은 불안정 정렬의 대표적 경우로, 노드의 값이 중복되는경우 계속해서 스왑을 시도한다.
  • 퀵 정렬은 최악의 경우, 첫번재 노드를 피벗으로 설정하고 불균형하게 분할정복을 시도하여 성능이 안좋아진다.
    • 속도는 알고리즘을 처리하고 결과를 도출하는 속도(주로 소프트웨어에 영향을 주고 받는다.)
    • 성능은 메모리에 영향을 주는 정도(주로 하드웨어에 영향을 주고 받는다.)

특징

  • 기본적으로 지원되는 내장 정렬 함수는 대부분 퀵 정렬을 기본으로 한다.
  • 일반적으로 원소의 개수가 적어질수록 나쁜 중간값이 선택될 확률이 높기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많다.
  • 병합 정렬과 퀵 정렬은 분할정복과 재귀 알고리즘을 사용한다는 측면에서는 유사해보이지만, 내부적으로 정렬을 하는 방식에서는 큰 차이가 있다.
  • 병합 정렬은 항상 정중앙을 기준으로 단순 분할 후 병합 시점에서 값의 비교 연산이 발생하는 반면, 퀵 정렬은 분할 시점부터 비교 연산이 일어나기 때문에, 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라서 아예 병합을 하지 않을 수 있다.

복잡도

  • 퀵 정렬의 성능은 어떻게 피벗값을 선택하느냐에 크게 달라질 수 있다.
  • 이상적인 경우 피벗값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되어 병합 정렬과 마찬가지로 O(NlogN)의 시간 복잡도를 가지게 된다.
  • 하지만 피벗값을 기준으로 분할했을 때 값들이 한편으로 크게 치우치면 성능이 저하되어 최악의 경우 한편으로 모든 값이 몰리므로 O($N^2$)의 시간 복잡도를 보인다.
  • 상용코드에서는 중앙값에 가까운 피벗값을 선택할 수 있는 섬세한 전략이 요구되며, 배열의 첫값과 중앙값 그리고 마지막값 중에 크기가 중간인 값을 사용하는 방법이 많이 사용된다.
  • 퀵 정렬의 공간복잡도는 구현 방법에 따라 달라질 수 있는데, 입력 배열이 차지하는 메모리만을 사용하는 in place sorting 방식으로 구현을 사용할 경우, O(1)의 공간 복잡도를 가진 코드의 구현이 가능하다.

최선의 경우

퀵소트_최선

최악의 경우

퀵소트_최악케이스

파이썬 소스 코드 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def quick_sort(arr):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = arr[(low + high) // 2]
        while low <= high:
            while arr[low] < pivot:
                low += 1
            while arr[high] > pivot:
                high -= 1
            if low <= high:
                arr[low], arr[high] = arr[high], arr[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(arr) - 1)

병합 정렬(Merge Sort)

Merge-Sort-Algorithm

  • 병합 정렬은 분할과 교체를 반복한다.
  • 병합 정렬은 일단 시간을 들여 1개의 서브리스트가 나올 때까지 분할을 진행한다.
    • 이후 배열값을 반복문을 통해 비교 -> 정렬 -> 교환 후 합치는 과정을 연속적으로 진행한다.

특징

  • 알고리즘을 큰 그림에서 보면 분할과 병합단계로 나눌 수 있으며, 단순히 중간 인덱스를 찾아야 하는 분할 비용보다 모든 값을 비교해야하는 병합 비용이 크다.
  • 전반적인 반복의 수는 점점 절반으로 줄어들기 때문에 O(logN) 시간이 필요하며, 각 패스에서 병합할 때 모든 값을 비교해야 하므로 O(N)의 시간이 필요하다. 총 시간 복잡도는 O(NlogN)이다.
  • 두 개의 배열을 병합할 때 병합 결과를 담아 놓을 배열이 추가로 필요하다. 따라서 공간 복잡도는 O(N)이다.
  • 다른 정렬 알고리즘과 달리 인접한 값들 간 스왑이 일어나지 않는다.

파이썬 소스코드 구현

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

최적화

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

참조

0%