Anonymous user
Sorting algorithms/Heapsort: Difference between revisions
D was not in it's correct alphabetical order
(D was not in it's correct alphabetical order) |
|||
Line 411:
[1 2 2 3 4 6 6]
</lang>
=={{header|D}}==▼
<lang d>import std.stdio, std.algorithm;▼
/// In-place HeapSort▼
public static void heapSort(Tseq)(Tseq seq) {▼
static void siftDown(Tseq seq, size_t start, size_t end) {▼
for (size_t root = start; root * 2 + 1 <= end; ) {▼
auto child = root * 2 + 1;▼
if (child + 1 <= end && seq[child] < seq[child + 1])▼
child++;▼
if (seq[root] < seq[child]) {▼
swap(seq[root], seq[child]);▼
root = child;▼
} else▼
break;▼
}▼
}▼
if (seq.length > 1)▼
for (size_t start = (seq.length - 2) / 2 + 1; start > 0; start--)▼
siftDown(seq, start - 1, seq.length - 1);▼
for (size_t end = seq.length - 1; end > 0; end--) {▼
swap(seq[end], seq[0]);▼
siftDown(seq, 0, end - 1);▼
}▼
}▼
void main() {▼
auto arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];▼
heapSort(arr);▼
writeln(arr);▼
}</lang>▼
=={{header|Common Lisp}}==
Line 525 ⟶ 493:
<pre>(heapsort (vector 1 9 2 8 3 7 4 6 5) '<) ; #(1 2 3 4 5 6 7 8 9)
(heapsort (list 9 8 1 2 7 6 3 4 5) '<) ; (1 2 3 4 5 6 7 8 9)</pre>
▲=={{header|D}}==
▲<lang d>import std.stdio, std.algorithm;
▲/// In-place HeapSort
▲public static void heapSort(Tseq)(Tseq seq) {
▲ static void siftDown(Tseq seq, size_t start, size_t end) {
▲ for (size_t root = start; root * 2 + 1 <= end; ) {
▲ auto child = root * 2 + 1;
▲ if (child + 1 <= end && seq[child] < seq[child + 1])
▲ child++;
▲ if (seq[root] < seq[child]) {
▲ swap(seq[root], seq[child]);
▲ root = child;
▲ } else
▲ break;
▲ }
▲ }
▲ if (seq.length > 1)
▲ for (size_t start = (seq.length - 2) / 2 + 1; start > 0; start--)
▲ siftDown(seq, start - 1, seq.length - 1);
▲ for (size_t end = seq.length - 1; end > 0; end--) {
▲ swap(seq[end], seq[0]);
▲ siftDown(seq, 0, end - 1);
▲ }
▲}
▲void main() {
▲ auto arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
▲ heapSort(arr);
▲ writeln(arr);
▲}</lang>
=={{header|E}}==
| |||