알고리즘 - 정렬(3) 병합 정렬, 힙 정렬, 도수 정렬
알고리즘
목차
- 버블 정렬
- 단순 선택 정렬
- 단순 삽입 정렬
- 셸 정렬
- 퀵 정렬
- 병합 정렬
- 힙 정렬
- 도수 정렬
6. 병합 정렬(Merge Sort)
병합 정렬 알아보기
병합 정렬은 컴퓨터 과학 역사상 최고의 천재라 일컬어지는 존 폰 노이만이 고안한 알고리즘으로, 분할정복의 진수를 보여주는 알고리즘이다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복한다. 최선과 최악 모두 O(n log n)인 사실상 완전한 O(n log n)으로 일정한 알고리즘이며, 대부분의 경우 퀵 정렬보다는 느리지만 일정한 실행 속도뿐만 아니라 안정 정렬(stable sort)이라는 점에서 상용 라이브러리에 많이 사용된다.
분할정복
주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 밀접하게 연관된 부분 문제를 다룬다. 전체 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고, 부분 문제를 재귀적으로 푼다. 그런 다음 찾은 해를 결합하여 원래 문제의 해를 만들어 낸다.
- 분할: 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.
- 정복: 부분 문제를 재귀적으로 풀어서 정복한다. 부분 문제의 크기가 충분히 작으면 직접적인 방법으로 푼다.
- 결합: 부분 문제의 해를 결합하여 원래 문제의 해가 되도록 만든다.
병합 정렬은 분할정복 기법을 아주 잘 이용한다.
- 분할: 정렬할 n개 원소의 배열을 n/2개 씩 부분 수열 두 개로 분할한다.
- 정복: 병합 정렬을 이용해 두 부분 배열을 재귀적으로 정렬한다.
- 결합: 정렬된 두 개의 부분 배열을 병합해 정렬된 배열 하나로 만든다.
병합 정렬 Pseudo Code
MERGE-SORT(A, p, r)
if p < r
q = ⌊(p+r)/2⌋
MERGE-SORT(A,p,q)
MERGE-SORT(A,q+1,r)
MERGE(A,p,q,r)정렬을 마친 배열의 병합
각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장한다. 이 작업을 반복하며 정렬을 마친 배열을 만든다.
from typing import Sequence, MutableSequence
def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
pa, pb, pc = 0, 0, 0 # 각 배열의 커서
na, nb, nc = len(a), len(b), len(c) # 각 배열의 원소 수
while pa < na and pb < nb:
if a[pa] <= b[pb]:
c[pc] = a[pa]
pa += 1
else:
c[pc] = b[pb]
pb += 1
pc += 1
while pa < na: # a에 남은 원소가 있으면 c에 복사
c[pc] = a[pa]
pa += 1
pc += 1
whle pb < nb: # b에 남은 원소가 있으면 c에 복사
c[pc] = b[pb]
pb += 1
pc += 1sorted() 함수로 병합 정렬하기
c= list(sorted(a+b))
a와 b를 연결하여 오름차순으로 정렬한 것을 list로 반환하여 c에 저장
a와 b가 정렬을 마친 상태가 아니어도 적용할 수 있다는 장점이 있지만, 속도가 빠르지 않다는 단점도 있다. 빠르게 병합하려면 heapq 모듈의 merge() 함수를 사용하면 된다.
import heapq
c = list(heapq.merge(a, b))
배열 a와 b를 병합하여 c에 저장
병합 정렬 만들기
정렬을 마친 배열의 병합을 응용하여 분할정복법에 따라 정렬하는 알고리즘을 병합 정렬이라고 한다.
배열의 원소 수가 2개 이상인 경우
1. 배열의 앞부분을 병합 정렬로 정렬한다.
2. 배열의 뒷부분을 병합 정렬로 정렬한다.
3. 배열의 앞부분과 뒷부분을 병합한다.
Code
from typing import MutableSequence
def merge_sort(a: MutableSequence) -> None:
def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
if left < right
center = (left+right) // 2
_merge_sort(a, left, center) # 배열 앞부분 병합정렬
_merge_sort(a, center+1, right) # 배열 뒷부분 병합정렬
p = j = 0
i = k = left
while i <= center:
buff[p] = a[i]
p += 1
i += 1
while i <= right and j < p:
if buff[j] <= a[i]:
a[k] = buff[j]
j += 1
else:
a[k] = a[i]
i += 1
k += 1
while j < p:
a[k] = buff[j]
k += 1
j += 1
n = len(a)
buff = [None] * n # 작업용 배열 생성
_merge_sort(a, 0, n-1) # 배열 전체를 병합 정렬
del buff # 작업용 배열을 소멸시간 복잡도
병합 배열의 시간 복잡도는 O(n)이다. 데이터 원소 수가 n일 때 병합 정렬의 단계는 log n 만큼 필요하므로 전체 시간 복잡도는 O(n log n)이다. 서로 떨어져 있는 원소를 교환하는 것이 아니므로 안정적이다.
7. 힙 정렬(Heap Sort)
힙 정렬 알아보기
힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙의 특성을 이용해 정렬하는 알고리즘이다. 힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전 이진 트리이다. 힙의 가장 위쪾에 위치한 루트가 가장 큰 값이 된다. 힙에서 자식 부모 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다. 따라서 힙은 부분 순서 트리(partial ordered tree)라고도 한다.
힙의 원소를 배열에 저장하는 방법은 우선 가장 위쪽에 있는 루트를 a[0]에 저장한다. 그리고 한 단계 아래에 왼쪽 원소부터 오른쪽 원소 순서로 배열에 저장한다.
부모 인덱스, 왼쪽 자식 인덱스, 오른쪽 자식 인덱스 사이 관계
원소 a[i]에서
- 부모: a[(i-1) // 2]
- 왼쪽 자식: a[i * 2 + 1]
- 오른쪽 자식: a[i * 2 + 2]
힙 정렬의 특징
'힙에서 최댓값은 루트에 위치한다.'는 특징을 이용하여 다음과 같은 작업을 반복한다.
- 힙에서 최댓값인 루트를 꺼낸다.
- 루트이외의 부분을 힙으로 만든다.
루트를 삭제한 힙의 재구성
- 루트를 꺼낸다.
- 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 루트로 이동한다.
- 루트에서 시작하여 자신보다 값이 큰 자식과 자리르 바꾸고 아래쪽으로 내려가는 작업을 반복한다.
- 자식의 값이 작거나 리프의 위치에 도달하면 종료한다.
힙 정렬 알고리즘 알아보기
- i값을 n-1로 초기화한다.
- a[0]과 a[i]를 교환한다.
- a[0], ..., a[i-1]을 힙으로 만든다.
- i값을 1씩 감소시켜 0이 되면 종료한다. 그렇지 않으면 2로 돌아간다.
배열을 힙으로 만들기
서브 트리도 힙을 재구성하는 방법을 통해 힙으로 만들 수 있다. 이방법으로 가장 아랫부분의 작은 서브트리부터 상향식(bottom-up)으로 진행하여 전체 배열을 힙으로 만들 수 있다.
Code
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
def down_heap(a: MutableSequence, left: int, right: int) -> None: # a[left] ~ a[right] 힙으로 만들기
temp = a[left] # 루트
parent = left
while parent < (right + 1) // 2:
cl = parent * 2 + 1 # 왼쪽 자식
cr = cl + 1 # 오른쪽 자식
child = cr if cr <= right and a[cr] > a[cl] else cl
if temp >= a[child]:
break
a[parent] = a[child]
parent = child
a[parent] = temp
n = len(a)
for i in range((n-1) // 2, -1, -1): # a[i]~a[n-1] 힙으로 만들기
down_heap(a, i, n-1)
for i in range(n-1, 0, -1):
a[0], a[i] = a[i], a[0] # 최댓값인 a[0]와 마지막 원소 교환
down_heap(a, 0, i-1) # a[0]~a[i-1]을 힙으로 만들기down_heap() 함수
배열 a에서 a[left]~a[right] 원소를 힙으로 만든다. a[left] 이외에는 모두 힙 상태라고 가정하고 a[left]를 아랫부분의 알맞은 위치로 옮겨 힙 상태를 만든다. (루트를 삭제한 힙의 재구성)
heap_sort() 함수
원소 수가 n인 배열 a를 힙 정렬하는 함수이다.
- 1단계: down_heap() 함수를 호출하여 배열 a를 힙으로 만든다.(배열을 힙으로 만들기)
- 2단계: 최댓값인 루트 a[0]을 꺼내 배열의 마지막 원소와 교환하고, 배열의 남은 부분을 다시 힙으로 만드는 과정을 반복하여 수행한다.(힙 정렬 알고리즘 알아보기)
시간 복잡도
힙 정렬은 선택 정렬을 응요한 알고리즘이다. 단순 선택 정렬은 아직 정렬하지 않은 부분의 모든 원소 중에서 최댓값을 선택한다. 힙 정렬은 맨 앞 원소를 꺼내는 것만으로 최댓값을 구할 수 있지만 남은 원소를 힙으로 재구성해야 한다.
단순 선택 정렬에서 최댓값인 원소를 선택하는 시간 복잡도는 O(n)이지만, 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(log n)이다. 루트를 알맞은 위치까지 내리는 작업은 스캔할 때마다 선택 범위가 절반으로 줄어드는 이진 검색과 비슷하다.
따라서 단순 선택 정렬의 시간 복잡도는 O(n2)이지만, 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는 데 걸리는 시간 복잡도는 O(n log n)으로 크게 줄어든다.
++heapq 모듈++
파이썬의 heapq 모듈은 힙에 원소를 추가하는 heappush() 함수와 힙에서 원소를 제거하는 heappop() 함수를 제공한다. 이때, 푸시와 팝은 힙의 조건을 유지하면 수행된다.
import heapq
from typing import MutableSequence
def heap_sort(a: MutableSequence) -> None:
heap = []
for i in a:
heapq.heappush(heap, i)
for i in range(len(a)):
a[i] = heapq.heappop(heap)8. 도수 정렬(Counting Sort)
도수 정렬 알아보기
도수 정렬은 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 분포수 세기(distribution counting) 정렬이라고도 한다. 지금까지 정리한 정렬 알고리즘에선 두 원소의 키값을 비교하여 정렬했다. 하지만 도수 정렬은 원소를 비교할 필요가 없다는 특징이 있다.
도수 정렬 만들기
- 도수 분포표 만들기
배열 a를 스캔하며 각 원솟값이 배열 f의 인덱스와 일치하는 곳에 카운트를 올리며 도수분포표를 만든다. - 누적 도수 분포표 만들기
배열 f의 두번째 원소부터 바로 앞의 원솟값을 더하는 과정을 통해 누적 도수 분포표를 만든다. - 작업용 배열 만들기
배열 a를 맨 끝에서 맨 앞으로 스캔하며 각 원솟값과 누적 도수 분포표 f를 대조하여 정렬을 완료한 배열을 만든다. - 배열 복사하기
정렬은 완료되었지만 정렬한 결과가 저장되는 것은 작업용 배열 b이므로 배열 a는 정렬하기 전의 상태이다. 그러므로 모든 원소를 배열 a에 복사한다.
Code
from typing import MutableSequence
def fsort(a: MutableSequence, max: int) -> None:
n = len(a)
f = [0] * (max+1)
b = [0] * n
for i in range(n):
f[a[i]] += 1
for i in range(1, max+1):
f[i] += f[i-1]
for i in range(n-1, -1, -1):
f[a[i]] -= 1
b[f[a[i]]] = a[i]
for i in range(n):
a[i] = b[i]
def counting_sort(a: MutableSequence) -> None:
fsort(a, max(a))도수 정렬 알고리즘은 데이터 비교﹒교환 작업이 필요 없어 매우 빠르다. 프로그램에서는 단일 for 문만 사용하고 재귀 호출이나 이중 if 문이 없어 매우 효율이 좋은 알고리즘이다. 하지만 도수 분포표가 필요하므로 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 적용할 수 있다.
각 단계(for 문)에서 배열 원소를 건너뛰지 않고 순서대로 스캔하므로 안정적이다. 그러나 3단계에서 배열 a를 스캔할 때 맨 앞부터 스캔하면 안정적이지 않다는 점을 주의해야 한다.
