지난 글: [알고리즘] - 삽입 정렬
힙 정렬(heap sort)은 힙이라는 데이터 구조를 사용하는 것이 특징이다. 힙에 대한 설명은 이전에 작성한 [알고리즘] - 힙에 있다.
1
7
/ \
6 5
/ \ / \
2 3 1 4힙에 1부터 7까지의 숫자를 저장한다. 힙은 내림차순으로 구축한다. 정렬하기 위해 힙에 저장된 숫자를 하나씩 꺼낸다.
◈내림차순 힙은 큰 것부터 순서대로 데이터를 추출하는 성질이 있으므로 꺼낸 숫자를 역순으로 나열하면 정렬이 완성된다.
2
(뿌리) 7// 꺼낸 숫자는 배열의 가장 오른쪽에 둔다.
/ \
6 5
/ \ / \
2 3 1 4먼저 뿌리에 잇는 숫자(7)을 꺼낸다.
3
힙을 재구축한다.
6 7
/ \
4 5
/ \ /
2 3 1같은 방식으로 뿌리에 있는 숫자(6)를 꺼내서 오른쪽에서 두 번째 칸에 둔다.
6 7
/ \
4 5
/ \ /
2 3 1
4
힙을 재구축한다.
5 6 7
/ \
4 1
/ \
2 3이후 힙이 모두 빌 때까지 같은 작업을 반복한다.
5
1 2 3 4 5 6 7모든 숫자를 힙에서 꺼내면 정렬이 완료된다.
참고 서적 :
