트리 정렬은 이진 탐색 트리(BST) 를 이용한다.
이진 탐색 트리를 중위 순회하면 키 값이 작은 순서대로 순회가 되므로 이를 그대로 저장하면 정렬이 완료된다.
Pseudocode 생략
소스 >>
# 트리 정렬 Implementation
# Jungtaek Lim(Heart), 2009-03-18
require 'binary_search_tree'
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 tree_sort(array)
bst = BinarySearchTree.new
array.each { |elem| bst.insert_node(elem, elem) }
sorted_array = bst.inorder_traversal
array.each_index { |i| array[i] = sorted_array[i].value }
end
array = make_example_array
tree_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 |
