분할 정복 정렬 알고리즘

Kyung yup Lee·2021년 4월 1일

알고리즘

목록 보기

24/33

분할정복

분할 정복이란 큰 문제를 잘게 쪼개서 해결하는 방식을 말한다. 재귀적인 개념을 내포하고 있고, top-down 방식으로 쪼개서 해결할 수도 있지만, bottom-up 방식으로 반복문을 통해 구현할 수도 있다.

또한 문제를 분할하면서 기존의 데이터를 모두 순회해야 했던 문제를 줄일 수 있어, 시간복잡도를 줄이는 데 좋다.

이런 특성을 이용해 정렬 알고리즘을 구현한 것이, quick sort 와 merge sort이다.

merge sort(합병 정렬)

합병 정렬은 이름과 같이 분할하고 합병을 하면서 정렬이 완성되는 알고리즘이다.

그림과 같이 작동하고, 먼저 분할이 이루어진 후에, return 하면서 정렬이 이루어진다.

O(n^2) 보다 빠른 이유는 병합하면서 정렬을 할 때, 모든 원소를 두번씩 순회할 필요 없이, 특정 원소 뒤에는 큰 원소 밖에 없다는 것을 확신할 수 있기 때문이다.

임시 배열이 반드시 필요하기 때문에, (분할 정렬된 조각 배열들을 저장해 둘) 공간복잡도를 O(n) 차지한다.

하지만 이를 통한 안정적인 O(nlogn)의 시간복잡도를 보장하기 때문에, 많이 사용하는 정렬 방식이다.

최악, 최선, 평균 모두 O(nlogn) 의 정렬 시간을 보장한다.

def merge_sort(x, low, high, arr):
    if low >= high:  # 길이가 1이라면 혹은 길이가 0일수도있음
        return

    mid = (low + high )// 2 # 미드를 결정해 주는 부분

    merge_sort(x, low, mid, arr) # 분할하는 부분(앞)
    merge_sort(x, mid + 1, high, arr) # 분할하는 부분(뒤)

    # 합쳐주는 방법
    i, j = low, mid + 1
    # low, mid+1 은 합병하는 내용인데 index 를 벗어나버릴 수도 있음 이걸 처리해줘야함
    for k in range(low, high + 1):
    	# 현재까지 분할 된 배열을 모두 순회 for문 한번으로 정렬이 가능
        if i > mid: # 왼쪽 배열은 mid 까지만 순회해야함. 그 이상가면 정렬할 배열을 초과
            # 배열을 초과할 경우 그 반대쪽 배열이 남아있다는 뜻이므로 그대로 임시 배열에 모두 붙여줌
            arr[k] = x[j]
            j += 1
        elif j > high: # 오른쪽 배열은 반대로 생각
            arr[k] = x[i]
            i += 1
        elif i <= mid and j <= high: # 만약 두 index가 모두 범위 안쪽이라면
            if x[i] > x[j]: # 왼쪽에 더 큰 수가 있으면 오른쪽 수를 임시배열에 붙임
                arr[k] = x[j]
                j += 1 
            else: # 오른쪽에 더 큰 수가 있으면 왼쪽배열의 수를 임시배열에 붙임
                arr[k] = x[i]
                i += 1
           # 이런 나이브한 구현이 가능한 이유는 분할 후 정복하면서 계속 정렬을 마치기 때문에, 
           # low ~ mid 사이의 배열과, mid ~ high 의 배열 사이에서는 정렬이 
           # 되어있다고(앞보다 뒤가 더 크다고) 보장할 수 있기 때문이다.
           
          
    x[low:high + 1] = arr[low:high + 1]
    # 해당 정렬된 배열을 x에 동기화 해주어야 한다. 
    return arr

quick sort(퀵 소트)

퀵소트는 분할정복을 한다는 면에서는 머지소트와 큰 차이는 없지만, 기준을 잡는 방법에서 다르다. 우선 머지소트는 반드시 절반으로 나눠서 구현을 했지만, 퀵 소트는 pivot을 지정해서 그 값을 기준으로 정렬을 한다. 때문에, 피벗을 잘못 선택할 경우(모든 피벗이 최대값이거나 최소값일 경우) 예를 들어 이미 정렬된 배열인데, 마지막 값을 피벗으로 지정할 경우, O(n^2) 이 나온다.

현실에서의 데이터가 이미 어느정도는 정렬이 되어 있고, 노이즈들이 발생하는 데이터가 많은 점으로 미루어보아, 퀵 소트가 오히려 O(n^2) 의 정렬 알고리즘보다 성능이 떨어지는 경우도 있다.

새로운 임시배열을 만들어서 값을 저장하는 방법을 통해 퀵 소트를 구현하면 공간복잡도는 O(logN)이 되지만, 훨씬 간단하게 구현이 가능하다.

반면 공간복잡도 O(1) 의 구현은 주어진 배열 내에서 스왑을 통해 구현하기 때문에 메모리는 절약 되지만, 훨씬 구현이 복잡하다.

시간 복잡도
- 최악의 경우: O(n^2)
- 최선의 경우: O(nlogn)
- 평균적인 경우: O(nlogn)

공간복잡도 O(logN)의 구현



def quick_sort(x):
    pivot = len(x)-1 # 피벗은 분할 배열의 마지막 원소로
    if len(x) == 0: # 분할한 배열이 0이라면 리턴
        return []
    arr1, arr2 = [], [
    
    for i in range(len(x)-1): # 배열 순회하면서
        if x[i] > x[pivot]: # 피벗보다 큰 원소는 
            arr2.append(x[i]) # 임시배열 arr2에 넣고
        else:
            arr1.append(x[i]) # 피벗보다 작거나 작은 원소

    return quick_sort(arr1) + [x[pivot]] + quick_sort(arr2)
print(quick_sort([3, 5, 321, 3, 6, 23, 1, 223]))

공간복잡도 O(1) 의 구현

퀵소트는 in-place 알고리즘으로 구현 가능하다. 공간복잡도는 절약하는게 좋지만, 구현이 복잡한 건 사실.

def quick_sort(x, start, end):
    if start >= end:
        return

    pivot = (start + end) // 2
    first_start = start
    first_end = end
    while start <= end:
        while x[start] < x[pivot]:  # 왼쪽 값 -> 더 큰 값있을경우 스왑
            start += 1

        while x[end] > x[pivot]:  # 오른쪽 값 -> 더 작은 값 스왑
            end -= 1

        if start <= end:
            x[start], x[end] = x[end], x[start]
            start += 1
            end -= 1

    quick_sort(x, first_start, start - 1)
    quick_sort(x, start, first_end)
    return x