자료구조/알고리즘 - Quicksort, Mergesort

Quicksort

퀵 정렬

분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘입니다.
배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide).
그리고 그 사이에 기준을 위치시킵니다.
작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다.

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i+1], part[pe] = part[pe], part[i+1]
        return i+1

    if len(lst) <= 1:
        return lst

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, p+1, end)
    quicksort(lst, start, p-1)
    return lst

print(quicksort([4, 6, 2, 9, 1], 0, 4))

Mergesort

 

입력이 2개의 부분 문제로 분할되고, 부분 문제의 크기가 1/2로 감소하는 분할 정복 알고리즘입니다.

즉, n개의 숫자들을 n/2개씩 2개의 부분문제로 분할하고, 각각의 부분 문제를 순환적으로 합병 정렬한 후, 2개의 정렬된 부분을 합병하여 정렬(정복)합니다. 즉, 합병 과정이 정복하는 것입니다.

병합 정렬

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


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

    mid = len(lst) // 2
    L = lst[:mid]
    R = lst[mid:]
    return merge(mergesort(L), mergesort(R))

Heapsort

import heapq

def sorted_by_heap(lst):
    heapq.heapify(lst)
    return [heapq.heappop(lst) for _ in range(len(lst))]


print(sorted_by_heap([5,7,9,3,2,1,6,8,9,0,6,4,3,2,6,1]))

오늘 푼 문제

https://geonoo.tistory.com/117

https://geonoo.tistory.com/118

https://geonoo.tistory.com/119

https://geonoo.tistory.com/120

https://geonoo.tistory.com/121

회고

퀵정렬, 병합정렬, 힙정렬에 대해서 간단히 배워 보고 구조를 다시 그려봤다.
문제들은 sort 내장 함수를 사용하면 간단히 풀리는 문제들이여서 쉽게 풀었다.

쉽게 풀려서 기분이 좋은것도 있지만 풀고나서 남는 시간에 다른걸 해봐야 했는데 시간을 잘 활용하지 못했다는 죄책감 같은게 있다.
산책다녀오고 나서 다시 문제 풀어봐야겠다.