Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Corpsmoderne (talk | contribs) |
m (→{{header|Sidef}}: updated code) |
||
| Line 5,586: | Line 5,586: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
<syntaxhighlight lang="ruby">func sift_down(a, start, end) { |
<syntaxhighlight lang="ruby">func sift_down(a, start, end) { |
||
var root = start |
var root = start |
||
while ((2*root + 1) <= end) { |
while ((2*root + 1) <= end) { |
||
var child = (2*root + 1) |
var child = (2*root + 1) |
||
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] |
||
root = child |
root = child |
||
} else { |
} else { |
||
return |
return nil |
||
} |
} |
||
} |
} |
||
} |
} |
||
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) |
sift_down(a, start, count-1) |
||
start -= 1 |
start -= 1 |
||
} |
} |
||
} |
} |
||
func heap_sort(a, count) { |
func heap_sort(a, count) { |
||
heapify(a, count) |
heapify(a, count) |
||
var end = (count - 1) |
var end = (count - 1) |
||
while (end > 0) { |
while (end > 0) { |
||
a[0, end] = a[end, 0] |
a[0, end] = a[end, 0] |
||
end -= 1 |
end -= 1 |
||
sift_down(a, 0, end) |
sift_down(a, 0, end) |
||
} |
} |
||
| Line 5,620: | Line 5,620: | ||
} |
} |
||
var arr = (1..10 -> shuffle) |
var arr = (1..10 -> shuffle) # creates a shuffled array |
||
say arr |
say arr # prints the unsorted array |
||
heap_sort(arr, arr.len) |
heap_sort(arr, arr.len) # sorts the array in-place |
||
say arr |
say arr # prints the sorted array</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9] |
<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9] |
||