Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
m (→‎version 1: added some verbage in the REXX section header (version 1). -- ~~~~)
(Updated second D entry)
Line 623: Line 623:
<lang d>import std.stdio, std.algorithm;
<lang d>import std.stdio, std.algorithm;


void inplaceHeapSort(R)(R seq) pure nothrow {
void heapSort(R)(R seq) pure nothrow @safe @nogc {
static void siftDown(R seq, in size_t start,
static void siftDown(R seq, in size_t start,
in size_t end) pure nothrow {
in size_t end) pure nothrow @safe @nogc {
for (size_t root = start; root * 2 + 1 <= end; ) {
for (size_t root = start; root * 2 + 1 <= end; ) {
auto child = root * 2 + 1;
auto child = root * 2 + 1;
Line 639: Line 639:


if (seq.length > 1)
if (seq.length > 1)
foreach_reverse (start; 1 .. (seq.length - 2) / 2 + 2)
foreach_reverse (immutable start; 1 .. (seq.length - 2) / 2 + 2)
siftDown(seq, start - 1, seq.length - 1);
siftDown(seq, start - 1, seq.length - 1);


foreach_reverse (end; 1 .. seq.length) {
foreach_reverse (immutable end; 1 .. seq.length) {
swap(seq[end], seq[0]);
swap(seq[end], seq[0]);
siftDown(seq, 0, end - 1);
siftDown(seq, 0, end - 1);
Line 649: Line 649:


void main() {
void main() {
auto arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
auto data = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0];
data.heapSort;
inplaceHeapSort(arr);
writeln(arr);
data.writeln;
}</lang>
}</lang>


Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"