힙 정렬(Heap Sort)
정의
이진 힙 삭제연산 메커니즘을 배열에 적용해서 정렬하는 알고리듬.
- 삭제된 걸 받아서 배열 -1 쪽 부터 정렬한다.
절차
오름차순 정렬을 위해서는 최대힙 사용. 내림차순 정렬 위해서는 최소힙 사용.
아래 과정은 오름차순 정렬을 예시로 든 것이다.
- 배열에 저장된 데이터들의 키를 우선순위로 삼아 최대 힙 구성
- 힙 가장 마지막 원소와 루트 R 교환. 힙 크기 1 감소(루트 R은 배열 가장 마지막에 정렬된 걸로 간주. 힙에서는 제외한다)
- 최대 힙 속성 유지 위해 루트R부터 다운힙
- 2~3 과정을 힙 크기 0 될때 까지 반복
예시
- 배열에 90, 80, … 이 값들을 각 데이터 키로 생각하자.
- 맨 처음 임의의 어떤 입력이 들어왔을 것이다. 그 입력을 최대힙 상태로 바꾼게 가장 왼쪽 첫 번째 그림이다.
- 맨 마지막 노드 90과 루트 40 교환 뒤. 90은 배열에는 남아있지만 힙에서는 삭제된 걸로 간주한다. 따라서 힙 크기 1 줄인다.
- 최대힙 속성 유지 위해 다운힙 한다. 40의 자식 60과 80 중 자식 승자는 80이다. 80과 40 교환한다. 최대힙 속성 유지 될 때 까지 40이 내려가면서 반복한다.
- 위 그림은 1회전 예다. 힙 크기가 0 될때 까지 위 과정을 반복한다.
힙 정렬 성능
시간복잡도
항상 $O(N\log{N})$ 걸린다. 입력에 전혀 영향 받지 않는다.
항상 효율적인 편이다.
- 초기 힙(최대힙/최소힙) 생성: $O(N)$ 시간
- 루트와 맨 마지막 노드 교환하고, 다운힙: $O(\log{N})$ $\Leftarrow$ 이진 힙 삭제연산 시간복잡도
- 위 두번째 과정(이진 힙 삭제연산) 총 $N-1$ 번 반복
따라서
$N + (N-1)*\log{N} = O(N\log{N})$
정렬 알고리듬 안정성(Stability)
안정성 보장하지 않는다.
곧, 정렬하고 나면 키값 같은 원소들의 상대적 위치 바뀔 수 있다.
힙 정렬 쓸모
입력에서 최댓값 또는 최솟값 뽑아 낼 때 유용하게 쓸 수 있다.
한편 힙 정렬은 메모리 많이 먹는다. 따라서 대용량 입력에는 비효율적이다.
힙 정렬 구현
힙 정렬 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 다운힙 정의
def downheap(i, hsize) : # 현재노드, 이진 힙 크기
# 다운힙 하기 위한 조건 : 왼쪽 자식이 있을 때
while (2*i <= hsize) :
k = 2*i # 왼쪽 자식 / 자식 승자
if k < hsize and a[k] < a[k+1] : # 오른쪽 자식이 있고 + 오른쪽 자식이 왼쪽 자식보다 크다면
k += 1 # 자식승자 (오른쪽 자식)
if a[i] >= a[k] :
break # 다운힙 그만한다
a[i], a[k] = a[k], a[i] # 루트와 자식승자 교환
i = k # 자식승자 자리가 다시 루트이자 현재노드가 된다.
# 초기 힙 생성 정의
def create_heap(a) :
hsize = len(a) - 1
for i in reversed(range(1, (hsize//2)+1)) : # 가장 아래 서브트리 루트~루트R 까지 다운 힙
downheap(i, hsize)
# 힙 정렬 정의
def heap_sort(a) :
N = len(a) - 1 # 맨 마지막 노드 이면서 동시에 이진 힙 크기
for i in range(N) :
a[1], a[N] = a[N], a[1] # 루트R과 제일 마지막 노드 교환
downheap(1, N-1)
N -= 1
힙 정렬 알고리듬 테스트
1
2
3
4
5
6
7
8
9
10
# 힙 정렬 알고리듬 테스트
a = [None,54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print('정렬 전:\t', end='')
print(a)
create_heap(a) # 최대 힙 생성
print(f'최대힙: {a}')
heap_sort(a)
print(f'힙 정렬 후(오름차순): {a}')
정렬 전: [None, 54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
최대힙: [None, 93, 88, 77, 26, 77, 31, 49, 20, 17, 54, 11, 17, 22, 44, 17, 10]
힙 정렬 후(오름차순): [None, 10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
heapq 활용한 힙 정렬
힙 정렬은 이진 힙 삭제연산을 배열에 적용한 것과 같다.
단지 삭제된 값을 받아서 배열에 다시 저장하는 것 뿐이다.
heapq.heappop()은 최소힙에서 삭제연산 구현해준다.
곧, 최솟값(루트R) 삭제 - 최소힙 속성 위해 다운힙 하는 알고리듬을 수행한다.
최소힙 속성 위해 다운힙 하면 다시 그 다음 최솟값이 루트 R에 올라올 것이다. 과정을 반복한다.
한편 매 삭제 과정에서 이진 힙에서 삭제된 루트R 값을 리스트에 append 함수로 추가해준다.
그러면 리스트 0번부터 -1까지 최솟값 ~ 최댓값 순으로 오름차순 정렬 될 것이다.
아래 코드는 위 생각을 코드로 구현한 것이다.
구현
1
2
3
4
5
6
7
8
# heapq 활용한 힙 정렬
import heapq
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
print(f'정렬 전: {a}')
heapq.heapify(a) # 배열을 최소힙으로 만드는 함수. 최대힙은 heapq._heapify_max('a')
print(f'힙: {a}')
정렬 전: [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
힙: [10, 11, 17, 17, 54, 17, 44, 20, 88, 77, 93, 31, 22, 77, 49, 26]
힙 정렬
1
2
3
4
5
# 힙 정렬
s = []
while a :
s.append(heapq.heappop(a))
힙 정렬 결과 출력
1
2
3
# 힙 정렬 결과 출력
print(f'heapq - 힙 정렬 이용해 오름차순 정렬 결과: {s}')
heapq - 힙 정렬 이용해 오름차순 정렬 결과: [10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
합병 정렬(Merge Sort)
정의
배열을 균일한 두 등분으로 나눈 뒤. 정렬하면서 합병하는 알고리듬
- 이러한 문제 해결 방식을 분할 정복 방법 이라고도 한다.
과정
- 배열을 더 이상 쪼갤 수 없을 때 까지 쪼갠다(크기 = 1)
- 크기 같은 것(또는 비슷한 것)들 끼리 서로 정렬하면서 합병한다
유의점
- 정렬은 합병할 때 함께 일어난다.
- 정렬 & 합병은 임시 리스트에서 일어난다.
- 정렬 & 합병 끝나면 결과를 원본 리스트에 덮어쓴다.
- 임시 리스트는 입력이 배열(Array) 일 때만 사용된다. 입력이 연결리스트일 때는 임시 리스트 사용 안 한다.
예시
- 가장 마지막 2개 부분리스트 정렬 & 합병 하는 과정만 좀 더 상세히 나타냈다.
- 두번째 그림 맨 아래 임시리스트를 원본 리스트에 덮어쓴다.
합병 정렬 구현
합병 정렬 정의
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# 합병정렬 정의
def merge_sort(a, b, low, high) :
if low >= high : return # 재귀중지, low=high:크기 1이라서 정렬 안한다, low > high: 정렬 할 게 없다
mid = low + (high-low)//2
merge_sort(a,b, low, mid)
merge_sort(a, b, mid+1, high)
merge(a,b,low, mid, high) # 재귀 결과, 정렬 & 합병 동시에 이루어진다.
# 합병 정의
# mid 와 high는 고정되어 있다.
def merge(a,b, low, mid, high) :
i = low # 앞쪽 리스트에서 포인터 현재위치
j = mid + 1 # 뒤쪽 리스트에서 포인터 현재위치
for k in range(low, high+1) : # k는 임시리스트 B 안에서 현재 위치
if (i > mid) : # 앞쪽 리스트 소진된 경우
b[k] = a[j]
j += 1
elif (j > high) : # 뒤쪽 리스트 소진된 경우
b[k] = a[i]
i += 1
elif (a[i] > a[j]) :
b[k] = a[j]
j += 1
else :
b[k] = a[i]
i += 1
for k in range(low, high+1) : # 임시배열에 저장된 정렬 결과 원래 배열에 덮어쓴다
a[k] = b[k]
합병 정렬 알고리듬 테스트
1
2
3
4
5
6
7
# 알고리듬 테스트 - 1
a = [2,3,1,6,7,5,4,9]
b = [None]*len(a)
print(f'정렬 전:{a}')
merge_sort(a,b, 0, len(a)-1)
print(f'정렬 후:{a}')
정렬 전:[2, 3, 1, 6, 7, 5, 4, 9]
정렬 후:[1, 2, 3, 4, 5, 6, 7, 9]
재귀호출 과정을 정리하면 아래와 같다.
- merge_sort(a,b, low=0, high=7)
- mid = 3
- merge_sort(a,b, low=0, mid=3) # 앞
- mid = 1
- merge_sort(a,b, low=0, mid = 1)
- mid = 0
- merge_sort(a, b, low=0, mid=0) # 정렬 x. 크기 1짜리다
- return
- merge_sort(a,b, mid+1=1, high=1) # 정렬 x. 크기 1짜리다
- return
merge(a,b, low=0, mid=0, high=1) $\Rightarrow$ 합병정렬. (0,1)위치 두 개 합병
- merge_sort(a,b, mid+1=2, high=3)
- mid = 2
- merge_sort(a,b, low=2, mid=2) # 정렬 x. 크기 1짜리다
- return
- merge_sort(a,b, mid+1=3, high=3) # 정렬 x. 크기 1짜리다
- return
merge(a,b, low=2, mid=2, high=3) $\Rightarrow$ 합병정렬. (2,3)위치 두 개 합병
merge(a,b, low=0, mid=1, high=3) $\Rightarrow$ 합병정렬. (0,1,2,3) 위치 정렬 & 합병 완료
- merge_sort(a, b, mid+1=4, high=7) # 뒤
- mid=5
- merge_sort(a,b, low=4, mid=5)
- mid=4
- merge_sort(a,b, low=4, mid=4) # 정렬 x. 크기 1짜리다
- return
- merge_sort(a,b, mid+1=5, high=5) # 정렬 x. 크기 1짜리다
- return
merge(a,b, low=4, mid=4, high=5) $\Rightarrow$ 합병정렬. (4,5)위치 두 개 합병
- merge_sort(a,b, mid+1=6, high=7)
- mid=6
- merge_sort(a,b, low=6, mid=6) # 정렬 x. 크기 1짜리다
- return
- merge_sort(a,b, mid+1=7, high=7) # 정렬 x. 크기 1짜리다
- return
merge(a, b, low=6, mid=6, high=7) $\Rightarrow$ 합병정렬. (6,7)위치 두 개 합병
merge(a,b, low=4, mid=5, high=7) $\Rightarrow$ 합병정렬. (4,5,6,7)위치 정렬 & 합병 완료
merge(a,b, low=0, mid=3, high=7) $\Rightarrow$ 합병정렬. 전체 정렬 & 합병 완료.
1
2
3
4
5
6
7
8
# 알고리듬 테스트 -2
a = [54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
b = [None]*len(a) # 임시배열
print(f'정렬 전:{a}')
merge_sort(a, b, 0, len(a)-1)
print(f'정렬 후:{a}')
정렬 전:[54, 88, 77, 26, 93, 17, 49, 10, 17, 77, 11, 31, 22, 44, 17, 20]
정렬 후:[10, 11, 17, 17, 17, 20, 22, 26, 31, 44, 49, 54, 77, 77, 88, 93]
합병 정렬 성능
시간복잡도
항상 $O(N\log{N})$ 시간복잡도 걸린다.
- 입력의 상태(데이터 분산 정도)에 영향 안 받는다.
- 입력 크기 $N$ 일 때. 합병 정렬이 비교연산에 쓰는 시간은 $O(N)$ 이다.
- 외부정렬 알고리듬이다. 전체 데이터는 하드에 저장되어 있고, 램에 일부만 불러온다. 램에 불러온 일부를 정렬한 뒤 하드에 저장하는 과정 반복한다. 결과로 하드에는 여러 개의 정렬된 블록이 들어있다. 이 블록들 병합은 하드 내에서 이루어진다. 곧, 전체 데이터의 정렬은 하드 내에서 이루어지는 셈이다. 속도가 느리다.
입력 크기
보통 $2^{k}$ 크기 입력을 받아 합병 정렬한다.