-
Notifications
You must be signed in to change notification settings - Fork 5
/
heap_sort.tig
107 lines (97 loc) · 3.11 KB
/
heap_sort.tig
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
let
type int_array = array of int
function print_array (arr: int_array) =
(
print("[");
for i:= 0 to array_length(arr) - 1 do print_arr_ele(arr[i]);
print("");
print("]")
)
function create_array(): int_array =
let
var size := 8
var arr := int_array [size] of 1
in
for i := 0 to size - 1 do arr[i] := random(50);
arr
end
function heap_sort(arr: int_array) =
let
var arr_size := array_length(arr)
var size := arr_size
function create_max_heap () =
let
var index := (arr_size - 1) / 2
in
while index >= 0 do
(
max_heapify(index, arr_size);
index := index - 1
)
end
function swap (a: int, b: int) =
let
var temp_a := arr[a]
var temp_b := arr[b]
in
arr[a] := temp_b;
arr[b] := temp_a
end
function max_heapify(index: int, size: int) =
let
var largest := arr[index]
var index_largest := index
var left_index := index * 2 + 1
var right_index := index * 2 + 2
in
if right_index < size & arr[right_index] > largest
then (largest := arr[right_index]; index_largest := right_index);
if left_index < size & arr[left_index] > largest
then (largest := arr[left_index]; index_largest := left_index);
if largest <> arr[index]
then (
swap(index, index_largest);
max_heapify(index_largest, size)
)
end
in
create_max_heap();
swap(0, arr_size - 1);
size := size - 1;
while size > 1 do (
max_heapify(0, size);
swap(0, size - 1);
size := size - 1
)
end
var arr := create_array()
/* This is for testing */
function create_array_test(): int_array =
let
var size := 5
var arr := int_array [size] of 1
in
for i := 0 to size - 1 do arr[i] := size-i-1;
arr
end
var arr_test := create_array_test()
in
print("Before sorting");
print_array(arr);
print("==============");
heap_sort(arr);
print("After sorting");
print_array(arr);
/* Testing start here */
assert_int(arr_test[0], 4);
assert_int(arr_test[1], 3);
assert_int(arr_test[2], 2);
assert_int(arr_test[3], 1);
assert_int(arr_test[4], 0);
heap_sort(arr_test);
assert_int(arr_test[0], 0);
assert_int(arr_test[1], 1);
assert_int(arr_test[2], 2);
assert_int(arr_test[3], 3);
assert_int(arr_test[4], 4)
end