[알고리즘] 01. 정렬 알고리즘 - 2

12 Jan 2020 in Computer-Science

다양한 정렬 알고리즘의 특징을 살펴본다.

어떤 데이터들을 정해진 순서대로 나열하는 여러 알고리즘 중 시간복잡도가 O(nlogn)인 대표적인 알고리즘을 살펴본다.

1. 병합 정렬

def merge_sort(lst):
    mid = len(lst)//2
    if mid <= 0:
        return lst

    L = merge_sort(lst[:mid])
    R = merge_sort(lst[mid:])

    return merge(L, R)


def merge(L, R):
    idx_l, idx_r = 0, 0
    len_l, len_r = len(L), len(R)
    merge_lst = []

    while idx_l < len_l or idx_r < len_r:
        if L[idx_l] <= R[idx_r]:
            merge_lst.append(L[idx_l])
            idx_l += 1
            if idx_l >= len_l:
                merge_lst.extend(R[idx_r:])
                break
        else:
            merge_lst.append(R[idx_r])
            idx_r += 1
            if idx_r >= len_r:
                merge_lst.extend(L[idx_l:])
                break

    return merge_lst

1. 데이터를 2ⁿ개의 단위로 분해한다.

2. 1의 과정에서 분해된 데이터를 두 단위씩 비교하며 작은값이 앞으로 오도록 결합한다.

3. 분해된 여러 단위들이 하나가 될때까지 2의 과정을 반복한다.

2. 퀵 정렬

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

    pivot = [lst[0]]
    L, R = [], []

    for idx in range(1, len(lst)):
        if lst[idx] < pivot[0]:
            L.append(lst[idx])
        elif lst[idx] > pivot[0]:
            R.append(lst[idx])
        else:
            pivot.append(lst[idx])
    return quick_sort(L) + pivot + quick_sort(R)

1. 선택한 데이터(pivot)를 기준으로 더 작은 값을 ‘왼쪽’, 더 큰값을 ‘오른쪽’으로 분리한다.

2. 분리된 두 구역에서 1의 방법을 더이상 분리되지 않을때까지 재귀적으로 반복한다.