[7일차] 04 정렬 : 04-5 병합 정렬, 04-6 기수 정렬

병합 정렬 (Merge Sort)

파이썬 구현

def merge_sort(arr):
    if len(arr) == 1: return arr

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

    left_arr = merge_sort(left)
    right_arr = merge_sort(right)
    return merge(left_arr, right_arr)

def merge(left, right):
    i, j = 0, 0 #투포인터
    sorted_arr = []

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1
    while i < len(left):
        sorted_arr.append(left[i])
        i += 1
    while j < len(right):
        sorted_arr.append(right[j])
        j += 1

    return sorted_arr

if __name__ == "__main__":
    A = [5, 7, 1, 3, 6, 5]
    print(merge_sort(A))  # [1, 3, 5, 5, 6, 7]

 

기수 정렬 (Radix Sort)

해당 자릿수만 비교

파이썬 구현

from collections import deque

def radix_sort(arr):
    buckets = [deque() for _ in range(10)] # 0~9 큐 만들기
    digit = 1 # 자릿수
    max_val = max(arr)
    queue = deque(arr)

    while (max_val >= digit):
        # 자릿수에 따라 bucket 채우기
        while queue:
            num = queue.popleft()
            buckets[(num // digit) % 10].append(num)
        # bucket 순서대로 queue에 다시 넣어주기
        for bucket in buckets:
            while bucket:
                queue.append(bucket.popleft())
        digit *= 10 # 자릿수 증가
    
    return list(queue)

if __name__ == "__main__":
    A = [5, 7, 1, 3, 6, 5]
    print(radix_sort(A))  # [1, 3, 5, 5, 6, 7]