Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
(Rename Perl 6 -> Raku, alphabetize, minor clean-up)
Line 842: Line 842:
}
}
</lang>
</lang>

=={{header|C sharp|C#}}==
<lang csharp>using System;
using System.Collections.Generic;
using System.Text;

public class HeapSortClass
{
public static void HeapSort<T>(T[] array)
{
HeapSort<T>(array, 0, array.Length, Comparer<T>.Default);
}

public static void HeapSort<T>(T[] array, int offset, int length, IComparer<T> comparer)
{
HeapSort<T>(array, offset, length, comparer.Compare);
}

public static void HeapSort<T>(T[] array, int offset, int length, Comparison<T> comparison)
{
// build binary heap from all items
for (int i = 0; i < length; i++)
{
int index = i;
T item = array[offset + i]; // use next item

// and move it on top, if greater than parent
while (index > 0 &&
comparison(array[offset + (index - 1) / 2], item) < 0)
{
int top = (index - 1) / 2;
array[offset + index] = array[offset + top];
index = top;
}
array[offset + index] = item;
}

for (int i = length - 1; i > 0; i--)
{
// delete max and place it as last
T last = array[offset + i];
array[offset + i] = array[offset];

int index = 0;
// the last one positioned in the heap
while (index * 2 + 1 < i)
{
int left = index * 2 + 1, right = left + 1;

if (right < i && comparison(array[offset + left], array[offset + right]) < 0)
{
if (comparison(last, array[offset + right]) > 0) break;

array[offset + index] = array[offset + right];
index = right;
}
else
{
if (comparison(last, array[offset + left]) > 0) break;

array[offset + index] = array[offset + left];
index = left;
}
}
array[offset + index] = last;
}
}

static void Main()
{
// usage
byte[] r = {5, 4, 1, 2};
HeapSort(r);

string[] s = { "-", "D", "a", "33" };
HeapSort(s, 0, s.Length, StringComparer.CurrentCultureIgnoreCase);
}
}</lang>


=={{header|C++}}==
=={{header|C++}}==
Line 922: Line 1,000:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
</pre>
</pre>

=={{header|C sharp|C#}}==
<lang csharp>using System;
using System.Collections.Generic;
using System.Text;

public class HeapSortClass
{
public static void HeapSort<T>(T[] array)
{
HeapSort<T>(array, 0, array.Length, Comparer<T>.Default);
}

public static void HeapSort<T>(T[] array, int offset, int length, IComparer<T> comparer)
{
HeapSort<T>(array, offset, length, comparer.Compare);
}

public static void HeapSort<T>(T[] array, int offset, int length, Comparison<T> comparison)
{
// build binary heap from all items
for (int i = 0; i < length; i++)
{
int index = i;
T item = array[offset + i]; // use next item

// and move it on top, if greater than parent
while (index > 0 &&
comparison(array[offset + (index - 1) / 2], item) < 0)
{
int top = (index - 1) / 2;
array[offset + index] = array[offset + top];
index = top;
}
array[offset + index] = item;
}

for (int i = length - 1; i > 0; i--)
{
// delete max and place it as last
T last = array[offset + i];
array[offset + i] = array[offset];

int index = 0;
// the last one positioned in the heap
while (index * 2 + 1 < i)
{
int left = index * 2 + 1, right = left + 1;

if (right < i && comparison(array[offset + left], array[offset + right]) < 0)
{
if (comparison(last, array[offset + right]) > 0) break;

array[offset + index] = array[offset + right];
index = right;
}
else
{
if (comparison(last, array[offset + left]) > 0) break;

array[offset + index] = array[offset + left];
index = left;
}
}
array[offset + index] = last;
}
}

static void Main()
{
// usage
byte[] r = {5, 4, 1, 2};
HeapSort(r);

string[] s = { "-", "D", "a", "33" };
HeapSort(s, 0, s.Length, StringComparer.CurrentCultureIgnoreCase);
}
}</lang>


=={{header|Clojure}}==
=={{header|Clojure}}==
Line 1,126: Line 1,126:
98 97 47 88 26 39 07 77 35 20 heapified
98 97 47 88 26 39 07 77 35 20 heapified
07 20 26 35 39 47 77 88 97 98 sorted</pre>
07 20 26 35 39 47 77 88 97 98 sorted</pre>



=={{header|CoffeeScript}}==
=={{header|CoffeeScript}}==
Line 1,406: Line 1,405:
}
}
}</lang>
}</lang>

=={{header|EasyLang}}==
=={{header|EasyLang}}==


Line 1,871: Line 1,871:


end program Heapsort_Demo</lang>
end program Heapsort_Demo</lang>

=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
<lang freebasic>' version 22-10-2016
<lang freebasic>' version 22-10-2016
Line 2,393: Line 2,394:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
</pre>
</pre>



=={{header|Julia}}==
=={{header|Julia}}==
Line 2,560: Line 2,560:
print
print
end sub</lang>
end sub</lang>



=={{header|Lobster}}==
=={{header|Lobster}}==
Line 2,738: Line 2,737:
heapsort(`a')
heapsort(`a')
show(`a')</lang>
show(`a')</lang>

=={{header|Maple}}==
=={{header|Maple}}==
<lang>swap := proc(arr, a, b)
<lang>swap := proc(arr, a, b)
Line 3,321: Line 3,321:
}
}
</lang>
</lang>

=={{header|Perl 6}}==
<lang perl6>sub heap_sort ( @list ) {
for ( 0 ..^ +@list div 2 ).reverse -> $start {
_sift_down $start, @list.end, @list;
}

for ( 1 ..^ +@list ).reverse -> $end {
@list[ 0, $end ] .= reverse;
_sift_down 0, $end-1, @list;
}
}

sub _sift_down ( $start, $end, @list ) {
my $root = $start;
while ( my $child = $root * 2 + 1 ) <= $end {
$child++ if $child + 1 <= $end and [<] @list[ $child, $child+1 ];
return if @list[$root] >= @list[$child];
@list[ $root, $child ] .= reverse;
$root = $child;
}
}

my @data = 6, 7, 2, 1, 8, 9, 5, 3, 4;
say 'Input = ' ~ @data;
@data.&heap_sort;
say 'Output = ' ~ @data;</lang>
{{out}}
<pre>
Input = 6 7 2 1 8 9 5 3 4
Output = 1 2 3 4 5 6 7 8 9
</pre>


=={{header|Phix}}==
=={{header|Phix}}==
Line 3,696: Line 3,664:
xs)
xs)
</lang>
</lang>

=={{header|Raku}}==
(formerly Perl 6)
<lang perl6>sub heap_sort ( @list ) {
for ( 0 ..^ +@list div 2 ).reverse -> $start {
_sift_down $start, @list.end, @list;
}

for ( 1 ..^ +@list ).reverse -> $end {
@list[ 0, $end ] .= reverse;
_sift_down 0, $end-1, @list;
}
}

sub _sift_down ( $start, $end, @list ) {
my $root = $start;
while ( my $child = $root * 2 + 1 ) <= $end {
$child++ if $child + 1 <= $end and [<] @list[ $child, $child+1 ];
return if @list[$root] >= @list[$child];
@list[ $root, $child ] .= reverse;
$root = $child;
}
}

my @data = 6, 7, 2, 1, 8, 9, 5, 3, 4;
say 'Input = ' ~ @data;
@data.&heap_sort;
say 'Output = ' ~ @data;</lang>
{{out}}
<pre>
Input = 6 7 2 1 8 9 5 3 4
Output = 1 2 3 4 5 6 7 8 9
</pre>


=={{header|REXX}}==
=={{header|REXX}}==
Line 4,259: Line 4,260:
setElementAt(setElementAt(list, i, vals.B), j, vals.A);
setElementAt(setElementAt(list, i, vals.B), j, vals.A);
</lang>
</lang>

=={{header|Sidef}}==
=={{header|Sidef}}==
<lang ruby>func sift_down(a, start, end) {
<lang ruby>func sift_down(a, start, end) {
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Heapsort"