[Algorithm] 병합 정렬, 퀵 정렬

병합 정렬 (Merge Sort)

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위까지 나눈 후, 차례대로 정렬하여 최종 결과 얻어냄
  • top-down 방식
• 시간 복잡도 : O(nlogn)

# 병합
def merge(left, right):
    # left: [1]
    # right: [3, 4, 5]
    result = []

    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))

    # ex)
    # result: [1]
    # left: []
    # right: [3, 4, 5]

    if len(right) > 0:
        result.extend(right)
    if len(left) > 0:
        result.extend(left)

    return result


# 분할
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)


arr = [5, 3, 7, 6, 2, 1, 4]
print(merge_sort(arr))

 

퀵 정렬 (Quick Sort)

• 주어진 배열을 두 개로 분할하고, 각각을 정렬
• 병합 정렬과 다른 점
  • 병합 정렬은 그냥 두 부분으로 나누는 반면,
    퀵정렬은 분할할 때 기준 아이템(pivot item) 중심으로 작은 것은 왼편, 큰 것은 오른편에 위치
  • 각 부분 정렬이 끝난 후, 병합 정렬은 병합이라는 후처리 작업 필요
  • 성능의 안정성 때문에 병합 정렬을 선호하는 편
    (혹은 언어에 내장된 정렬 함수를 사용하는 것이 바람직, 파이썬의 경우 tim sort)
  • 퀵 정렬은 병합 정렬과 다르게 불안정 정렬 (똑같은 숫자가 존재한다면, 똑같은 숫자의 정렬 순서가 보장되지 않음)
• 퀵소트의 평균 시간 복잡도 : O(nlogn)
• 퀵소트의 최악 시간 복잡도 : O(n^2)

 

• 퀵정렬 간단 버전

def quick_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]

    less = []
    equal = []
    more = []

    for num in arr:
        if num < pivot:
            less.append(num)
        elif num == pivot:
            equal.append(num)
        else:
            more.append(num)

    return quick_sort(less) + equal + quick_sort(more)


arr = [5, 3, 7, 6, 2, 1, 4]
print(quick_sort(arr))

• 퀵정렬 정석 버전

def partition(arr, start, end):
    # 배열의 맨 오른쪽 값으로 피봇 설정
    pivot = arr[end]

    left = start
    right = end - 1 
    
    while left < right:
        # 왼쪽(left)은 피봇보다 큰 값을 찾을 때까지 오른쪽 전진
        while arr[left] <= pivot:
            left += 1
            if left > right:
                break
        
        # 오른쪽(right)은 피봇보다 작은 값을 찾을 때까지 왼쪽 전진
        while arr[right] >= pivot:
            right -= 1
            if left > right:
                break

        # 만약, 아직 서로의 위치가 유효하다면 (left < right)
        # 아직 교환할 값이 있다는 뜻이므로 교환!
        if left <= right:
            arr[left], arr[right] = arr[right], arr[left]
        
    # 피봇의 위치가 완전히 결정되었으므로
    # left 위치의 값과 피봇 위치(end)의 값을 교환
    arr[left], arr[end] = arr[end], arr[left]

    # 결정된 피봇의 위치가 left
    return left


def quick_sort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end) # 매 시행마다 새로운 left 반환, 이게 새로운 피봇이 됨
        quick_sort(arr, start, pivot-1) # 왼쪽 서브 배열 재귀적으로 실행
        quick_sort(arr, pivot+1, end)


arr = [5, 3, 7, 6, 2, 1, 4]
quick_sort(arr, 0, len(arr)-1)
print(arr)