Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
(Added EchoLisp) |
m (→{{header|Sidef}}: minor code simplifications) |
||
| Line 3,087: | Line 3,087: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
<lang ruby>func |
<lang ruby>func sift_down(a, start, end) { |
||
var root = start; |
var root = start; |
||
while ((2*root + 1) <= end) { |
while ((2*root + 1) <= end) { |
||
| Line 3,093: | Line 3,093: | ||
if ((child+1 <= end) && (a[child] < a[child + 1])) { |
if ((child+1 <= end) && (a[child] < a[child + 1])) { |
||
child += 1; |
child += 1; |
||
} |
} |
||
if (a[root] < a[child]) { |
if (a[root] < a[child]) { |
||
a[child, root] = a[root, child]; |
a[child, root] = a[root, child]; |
||
| Line 3,102: | Line 3,102: | ||
} |
} |
||
} |
} |
||
func heapify(a, count) { |
func heapify(a, count) { |
||
var start = ((count - 2) / 2); |
var start = ((count - 2) / 2); |
||
while (start >= 0) { |
while (start >= 0) { |
||
sift_down(a, start, count-1); |
|||
start -= 1; |
start -= 1; |
||
} |
} |
||
} |
} |
||
func |
func heap_sort(a, count) { |
||
heapify(a, count); |
heapify(a, count); |
||
var end = (count - 1); |
var end = (count - 1); |
||
| Line 3,117: | Line 3,117: | ||
a[0, end] = a[end, 0]; |
a[0, end] = a[end, 0]; |
||
end -= 1; |
end -= 1; |
||
sift_down(a, 0, end) |
|||
} |
} |
||
return a |
|||
} |
} |
||
var arr = (1..10 shuffle); # creates a shuffled array |
var arr = (1..10 -> shuffle); # creates a shuffled array |
||
say arr |
say arr; # prints the unsorted array |
||
heap_sort(arr, arr.len); # sorts the array in-place |
|||
say arr |
say arr; # prints the sorted array</lang> |
||
{{out}} |
{{out}} |
||
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9] |
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9] |
||