힙 정렬은 힙을 이용하여 자료를 정렬하는 방법이다.
잠깐 힙 내용을 돌아보자면, Max Heap 의 경우 루트가 힙의 전체 노드 중 가장 큰 키 값을 가지며, Min Heap 의 경우 루트가 힙의 전체 노드 중 가장 작은 값을 가지게 된다.
이를 이용하여 집합의 원소들을 전부 힙에 넣고 계속 루트를 삭제하면서 삭제되는 노드를 저장하면 정렬이 완료된다.
힙만 만들어져 있으면 아주 간단하므로 Pseudocode 도 생략한다.
보고 있는 책에서는 힙 공간을 새로 만들지 않기 위해서 정렬할 배열을 재정리해서 힙으로 만들고 그 안에서 삭제하고 저장하는데…
복잡하다… 보다는 귀찮고 시간 아깝다. 언제 다시 쓰게 될지도 모르는데… 그냥 있는 거 활용하자.
소스 >>
# 힙 정렬 Implementation
# Jungtaek Lim(Heart), 2009-03-18
# Min-Heap 사용
require 'heap'
def make_example_array
array = [69, 10, 30, 2, 16, 8, 31, 22]
end
def print_array(array)
puts array.map {|x| x.to_s + " "}.to_s
end
def heap_sort(array)
heap = Heap.new(false)
array.each { |elem| heap.insert_data(elem, elem) }
i = 0
while true
node = heap.delete_data
break if node == nil
array[i] = node.value
i += 1
end
end
array = make_example_array
heap_sort array
print_array array
|
결과 >>
2 8 10 16 22 30 31 69
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 이진 검색 - in Ruby (0) | 2009/03/18 |
|---|---|
| 트리 정렬 - in Ruby (0) | 2009/03/18 |
| 힙 정렬 - in Ruby (0) | 2009/03/18 |
| 기수 정렬 - in Ruby (0) | 2009/03/18 |
| 병합 정렬 - in Ruby (0) | 2009/03/18 |
| 셸 정렬 - in Ruby (0) | 2009/03/18 |
