Written by Lee Jongseo
on May 21, 2021

Alogrithm[3]:⭐ - Merge Sort, Quick Sort.

Divide and Conquer

One of an algorithmic design pattern that use recursion

세 가지 단계로 이루어져 있다.

Divide: input size를 한 개 이상의 기준에 따라 나눈다.(Ex. 한 개의 Set를 두 개의 subset으로 나눔)
Conquer: subset를 재귀적으로 solve한다.(정렬의 경우, subset을 재귀적으로 정렬한다.)
Combine: solved subset를 merge한다.

Merge Sort

분할 정복을 이용한 정렬 알고리즘

input: number를 요소로 하는 리스트 output: 정렬된 리스트

Divide: 리스트를 가운데 인덱스를 기준으로 둘 로 나눈다.
Conquer: 나눈 두 개의 sub 리스트를 Merge sort한다.
merge: 정렬 된 두 개의 sub 리스트를 병합한다.

Code

def msort(L):
    # 합병하는 유틸리티 함수
    # 두 개의 서브 리스트(S1, S2)를 L에 합병한다.
    def merge(S1, S2, L):
        i = j = 0
        # 인덱스 포인터를 이용하여 비교를 수행한다.
        # 비교과정을 거쳐 L에 정렬된 상태로 합병한다.
        while i + j < len(L):
            if (j == len(S2) or (i < len(S1) and S1[i] < S2[j])):
                L[i+j] = S1[i]
                i += 1
            else:
                L[i+j] = S2[j]
                j += 1

    # 리스트 요소가 하나일 경우, 정렬된 상태.
    # 재귀 호출을 중단하는 기준 시점.
    if len(L) < 2:
        return
    mid = len(L) // 2 # mid index
    # 가운데를 기준으로 두 개의 Sublist로 분할한다.
    S1: L[:mid] 
    S2: L[mid:]
    # 분할한 서브리스트를 다시 병합정렬 한다.
    msort(S1)
    msort(S2)
    # original 리스트에 다시 합병한다.
    merge(S1, S2, L)

Quick Sort

분할의 기준이 되는 pivot을 설정하여 정렬하는 알고리즘

Pivot을 설정한다. (Ex. 맨 앞 요소를 pivot으로 설정)
Pivot보다 작은 값은 pivot 왼쪽(left)에, 큰 값은 오른 쪽(right)에 위치
pivot 왼쪽을 다시 quick sort한다.
pivot을 리턴한다.
pivot 오른쪽을 quick sort 한다.

code

def qsort(L):
    # 요소가 한 개거나 없다면 그대로 반환한다.
    # 재귀 호출 중단 조건
    if len(L) < 2:
        return L
    # 피봇 설정
    pivot = L[0]
    # 왼쪽과 오른쪽으로 분할한다.
    left = [item for item in L[1:] if pivot > item]
    right = [item for item in L[1:] if pivot < item]
    # 합친다.
    return qsort(left) + [pivot] + qsort(right)

👈 👉 Top