3. 정렬 알고리즘

정렬 알고리즘은 다양한 아이디어를 포함하고 있습니다. 정렬만 하더라도 문제가 쉬워지는 경우가 있기에 꼭 알아야하는 알고리즘이기도 합니다.

정렬에 따른 장단점과 시간복잡도를 알아봅시다.

퀵 정렬과 머지 정렬은 따로 구현은 하지 않았습니다. 두 개는 이론을 중심으로 알아두는 것을 추천합니다.

아래 세 정렬은 시간복잡도가 \(O(N^2)\) 인 정렬입니다.

3-1. 선택정렬 (Selection Sort)

선택정렬의 핵심은 반복문 1번에 최솟값 또는 최댓값을 알 수 있다는 점입니다.

# lst : list, N : length
def selection_sort(lst, N):
    for i in range(N):
        min_idx = i
        for j in range(i+1, N):
            if lst[i] > lst[j] : min_idx = j
        lst[i] = j
    return lst

3-2. 버블정렬 (Bubble Sort)

버블정렬의 핵심은 이웃된 값을 비교하여 순서를 바꾸면 1회 순회마다 최솟값 또는 최댓값을 끝으로 보낼 수 있다는 점입니다.

# lst : list, N : length
def selection_sort(lst, N):
    for i in range(N):
        for j in range(i, N-1):
            if lst[j] > lst[j+1] : lst[i], lst[j] = lst[j], lst[i]
    return lst

3-3. 삽입 정렬 (Insertion Sort)

이 정렬은 이미 정렬된 부분 수열에서 자신의 위치를 찾아가는 방법을 사용합니다.

여기서부터는 시간복잡도가 \(O(nlogn)\)인 정렬 알고리즘 입니다.

3-3. 퀵 정렬 (Quick Sort)

퀵 정렬은 말그대로 빠른 정렬 방법입니다. 이 알고리즘의 핵심은 분할정복입니다.

기준점을 가지고 배열의 원소를 나누는 방법

3-4. 병합 정렬 (Merge Sort)

병합 정렬은 분할 정복을 바탕으로 한 정렬 방법입니다. 이 알고리즘의 핵심은 분할정복입니다.

정렬된 두 배열로 정렬된 배열을 만드는 방법 (merge)

재귀적으로 배열을 2개씩 나누고, 길이가 1인 배열부터 차근차근 merge하는 것이 핵심입니다.

def merge(l_lst, r_lst):
    l_len, r_len = len(l_lst), len(r_lst)
    ret, lp, rp = [], 0, 0
    while lp < l_len and rp < r_len:
        if l_lst[lp] <= r_lst[rp]:
            ret.append(l_lst[lp])
            lp += 1
        else:
            ret.append(r_lst[rp])
            rp += 1
    return ret + l_lst[lp:] + r_lst[rp:]


def merge_sort(lst):
    if len(lst) == 1: return lst
    size = len(lst)//2
    l_lst, r_lst = lst[:size], lst[size:]
    l_lst, r_lst = merge_sort(l_lst), merge_sort(r_lst)
    return merge(l_lst, r_lst)

3-5. 힙 정렬 (Heap Sort)

앞서 공부한 Heap이라는 자료구조를 활용하면 쉽게 정렬할 수 있습니다. Heap은 최소 또는 최대 값을 항상 꺼내올 수 있습니다.

그렇다면 모든 원소를 Heap에 넣고, 하나씩 빼면 자동으로 정렬되지 않을까요?

from heapq import *

def heapsort(lst):
    heapify(lst)
    return [heappop(lst) for i in range(len(lst))]

3-6. 기수 정렬 (Radix Sort)

알고리즘에서는 종종 메모리와 시간의 trade-off가 있습니다.

def radix_sort(lst, N):
    MN, MX = min(lst), max(lst)
    sorted_lst = [0 for _ in range(MX-MN+1)]
    for val in range(lst):
        sorted_lst[val-MN] += 1
    ret = [] # sorted array
    for idx, val in enumerate(range(MX-MN+1)):
        if val > 0 : 
            for _ in range(val) : ret.append(idx)
    return ret

Chapter. 3