기록하는 공간

정렬 2 - 퀵 정렬, 힙 정렬 정리

05 Nov 2019

퀵 정렬(Quick Sort)

분할 정복(Divide-and-conquer)

분할 정복은 재귀적 알고리즘으로 세 부분으로 나누어 볼 수 있다.

  1. 분할: 원래 문제를 분할하여 비슷한 유형의 더 작은 하위 문제로 나누기
  2. 정복: 하위 문제 각각을 재귀적으로 해결하기
  3. 합치기: 하위 문제의 답을 합쳐서 원래 문제 해결하기

퀵 정렬은 이런 분할 정복을 이용한다. 먼저 배열에서 원소 하나를 고른다. 이 원소는 기준 원소 또는 피벗(pivot)이라 부른다. 그 다음, 피벗을 기준으로 피벗보다 작은 원소와 큰 원소로 나눈다. 이 과정이 분할이며 분할하여 나뉘어진 각 하위 배열을 같은 과정을 반복하는 것이 정복이 되며 모든 배열이 끝까지 정렬이 된 후 합치면 퀵 정렬을 마치게 된다. 퀵 정렬은 피벗의 선택이 성능에 영향을 미치는데 최악의 경우는 O(n²)이지만 평균적으로는 O(n log n)의 시간이 소요된다.

예제

def quick_sort(seq):
    if len(seq) < 2:
        return seq
    
    pivot = seq[0]
    less = [i for i in seq[1:] if i <= pivot]
    greater = [i for i in seq[1:] if i > pivot]
    
    return quicksort(less) + [pivot] + quicksort(greater)

힙 정렬(Heap Sort)

힙 정렬은 힙의 개념을 이용하여 정렬한다.

  1. 정렬할 데이터를 이진 트리 중 최대 힙의 형태로 구성
  2. 최대 힙의 형태로 구성된 이진 트리에서 취상위 데이터 꺼내기
  3. 나머지 데이터를 가지고 최대 힙 구조의 이진 트리 구성

예제

def heap_sort(seq):
    for start in range((len(seq)-2)//2, -1, -1):
        sift_down(seq, start, len(seq)-1)
    
    for end in range(len(seq)-1, 0, -1):
		seq[end], seq[0] = seq[0], seq[end]
        sift_down(seq, 0, end-1)
    
    return seq

def sift_down(seq, start, end):
    root = start
    while True:
        child = root * 2 + 1
        if child > end:
            break
        if child + 1 <= end and seq[child] < seq[child + 1]:
            child += 1
        if seq[root] < seq[child]:
            seq[root], seq[child] = seq[child], seq[root]
            root = child
        else:
            break 

# heapq 라이브러리 사용


import heapq

def heap_sort(seq):
    h = []
    for value in seq:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]
참조

그림으로 개념을 이해하는 알고리즘 그림으로 정리한 알고리즘과 자료구조 파이썬 자료구조와 알고리즘

Related Posts