Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted
m (syntax highlighting fixup automation)
Line 67: Line 67:
{{trans|Python}}
{{trans|Python}}


<lang 11l>F siftdown(&lst, start, end)
<syntaxhighlight lang="11l">F siftdown(&lst, start, end)
V root = start
V root = start
L
L
Line 91: Line 91:
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
heapsort(&arr)
heapsort(&arr)
print(arr)</lang>
print(arr)</syntaxhighlight>


{{out}}
{{out}}
Line 101: Line 101:
{{trans|PL/I}}
{{trans|PL/I}}
The program uses ASM structured macros and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
The program uses ASM structured macros and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
<lang 360asm>* Heap sort 22/06/2016
<syntaxhighlight lang="360asm">* Heap sort 22/06/2016
HEAPS CSECT
HEAPS CSECT
USING HEAPS,R13 base register
USING HEAPS,R13 base register
Line 235: Line 235:
N DC A((N-A)/L'A) number of items
N DC A((N-A)/L'A) number of items
YREGS
YREGS
END HEAPS</lang>
END HEAPS</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 243: Line 243:
=={{header|AArch64 Assembly}}==
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
<lang AArch64 Assembly>
/* ARM assembly AARCH64 Raspberry PI 3B */
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program heapSort64.s */
/* program heapSort64.s */
Line 481: Line 481:
/* for this file see task include a file in language AArch64 assembly */
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
.include "../includeARM64.inc"
</syntaxhighlight>
</lang>
=={{header|ActionScript}}==
=={{header|ActionScript}}==
<lang ActionScript>function heapSort(data:Vector.<int>):Vector.<int> {
<syntaxhighlight lang="actionscript">function heapSort(data:Vector.<int>):Vector.<int> {
for (var start:int = (data.length-2)/2; start >= 0; start--) {
for (var start:int = (data.length-2)/2; start >= 0; start--) {
siftDown(data, start, data.length);
siftDown(data, start, data.length);
Line 511: Line 511:
}
}
}
}
}</lang>
}</syntaxhighlight>


=={{header|Ada}}==
=={{header|Ada}}==
This implementation is a generic heapsort for unconstrained arrays.
This implementation is a generic heapsort for unconstrained arrays.
<lang Ada>generic
<syntaxhighlight lang="ada">generic
type Element_Type is private;
type Element_Type is private;
type Index_Type is (<>);
type Index_Type is (<>);
type Collection is array(Index_Type range <>) of Element_Type;
type Collection is array(Index_Type range <>) of Element_Type;
with function "<" (Left, right : element_type) return boolean is <>;
with function "<" (Left, right : element_type) return boolean is <>;
procedure Generic_Heapsort(Item : in out Collection);</lang>
procedure Generic_Heapsort(Item : in out Collection);</syntaxhighlight>
<lang Ada>procedure Generic_Heapsort(Item : in out Collection) is
<syntaxhighlight lang="ada">procedure Generic_Heapsort(Item : in out Collection) is
procedure Swap(Left : in out Element_Type; Right : in out Element_Type) is
procedure Swap(Left : in out Element_Type; Right : in out Element_Type) is
Temp : Element_Type := Left;
Temp : Element_Type := Left;
Line 570: Line 570:
end loop;
end loop;
end Generic_Heapsort;</lang>
end Generic_Heapsort;</syntaxhighlight>
Demo code:
Demo code:
<lang Ada>with Generic_Heapsort;
<syntaxhighlight lang="ada">with Generic_Heapsort;
with Ada.Text_Io; use Ada.Text_Io;
with Ada.Text_Io; use Ada.Text_Io;


Line 590: Line 590:
end loop;
end loop;
New_Line;
New_Line;
end Test_Generic_Heapsort;</lang>
end Test_Generic_Heapsort;</syntaxhighlight>


=={{header|ALGOL 68}}==
=={{header|ALGOL 68}}==
<lang algol68>#--- Swap function ---#
<syntaxhighlight lang="algol68">#--- Swap function ---#
PROC swap = (REF []INT array, INT first, INT second) VOID:
PROC swap = (REF []INT array, INT first, INT second) VOID:
(
(
Line 644: Line 644:
print(("After: ", a))
print(("After: ", a))


)</lang>
)</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 654: Line 654:
=={{header|AppleScript}}==
=={{header|AppleScript}}==
===Binary heap===
===Binary heap===
<lang applescript>-- In-place binary heap sort.
<syntaxhighlight lang="applescript">-- In-place binary heap sort.
-- Heap sort algorithm: J.W.J. Williams.
-- Heap sort algorithm: J.W.J. Williams.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
Line 716: Line 716:
set aList to {74, 95, 9, 56, 76, 33, 51, 27, 62, 55, 86, 60, 65, 32, 10, 62, 72, 87, 86, 85, 36, 20, 44, 17, 60}
set aList to {74, 95, 9, 56, 76, 33, 51, 27, 62, 55, 86, 60, 65, 32, 10, 62, 72, 87, 86, 85, 36, 20, 44, 17, 60}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</lang>
return aList</syntaxhighlight>


{{output}}
{{output}}
<lang applescript>9, 10, 17, 20, 27, 32, 33, 36, 44, 51, 55, 56, 60, 60, 62, 62, 65, 72, 74, 76, 85, 86, 86, 87, 95}</lang>
<syntaxhighlight lang="applescript">9, 10, 17, 20, 27, 32, 33, 36, 44, 51, 55, 56, 60, 60, 62, 62, 65, 72, 74, 76, 85, 86, 86, 87, 95}</syntaxhighlight>


===Ternary heap===
===Ternary heap===
<lang applescript>-- In-place ternary heap sort.
<syntaxhighlight lang="applescript">-- In-place ternary heap sort.
-- Heap sort algorithm: J.W.J. Williams.
-- Heap sort algorithm: J.W.J. Williams.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
on heapSort(theList, l, r) -- Sort items l thru r of theList.
Line 792: Line 792:
set aList to {75, 46, 8, 43, 20, 9, 25, 89, 19, 29, 16, 71, 44, 23, 17, 99, 79, 97, 19, 75, 32, 27, 42, 93, 75}
set aList to {75, 46, 8, 43, 20, 9, 25, 89, 19, 29, 16, 71, 44, 23, 17, 99, 79, 97, 19, 75, 32, 27, 42, 93, 75}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</lang>
return aList</syntaxhighlight>


{{output}}
{{output}}
<lang applescript>{8, 9, 16, 17, 19, 19, 20, 23, 25, 27, 29, 32, 42, 43, 44, 46, 71, 75, 75, 75, 79, 89, 93, 97, 99}</lang>
<syntaxhighlight lang="applescript">{8, 9, 16, 17, 19, 19, 20, 23, 25, 27, 29, 32, 42, 43, 44, 46, 71, 75, 75, 75, 79, 89, 93, 97, 99}</syntaxhighlight>


=={{header|ARM Assembly}}==
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
<lang ARM Assembly>


/* ARM assembly Raspberry PI */
/* ARM assembly Raspberry PI */
Line 1,090: Line 1,090:
iMagicNumber: .int 0xCCCCCCCD
iMagicNumber: .int 0xCCCCCCCD


</syntaxhighlight>
</lang>


=={{header|Arturo}}==
=={{header|Arturo}}==


<lang rebol>siftDown: function [items, start, ending][
<syntaxhighlight lang="rebol">siftDown: function [items, start, ending][
root: start
root: start
a: new items
a: new items
Line 1,126: Line 1,126:
]
]


print heapSort [3 1 2 8 5 7 9 4 6]</lang>
print heapSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>


{{out}}
{{out}}
Line 1,134: Line 1,134:


=={{header|AutoHotkey}}==
=={{header|AutoHotkey}}==
<lang AutoHotkey>heapSort(a) {
<syntaxhighlight lang="autohotkey">heapSort(a) {
Local end
Local end
end := %a%0
end := %a%0
Line 1,167: Line 1,167:
heapSort("a")
heapSort("a")
ListVars
ListVars
MsgBox</lang>
MsgBox</syntaxhighlight>


=={{header|BBC BASIC}}==
=={{header|BBC BASIC}}==
<lang bbcbasic> DIM test(9)
<syntaxhighlight lang="bbcbasic"> DIM test(9)
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1
PROCheapsort(test())
PROCheapsort(test())
Line 1,204: Line 1,204:
IF a(r%) < a(c%) SWAP a(r%), a(c%) : r% = c% ELSE ENDPROC
IF a(r%) < a(c%) SWAP a(r%), a(c%) : r% = c% ELSE ENDPROC
ENDWHILE
ENDWHILE
ENDPROC</lang>
ENDPROC</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,211: Line 1,211:


=={{header|BCPL}}==
=={{header|BCPL}}==
<lang BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.
<syntaxhighlight lang="bcpl">// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.


GET "libhdr.h"
GET "libhdr.h"
Line 1,252: Line 1,252:
}
}
newline()
newline()
}</lang>
}</syntaxhighlight>


=={{header|C}}==
=={{header|C}}==
<lang c>#include <stdio.h>
<syntaxhighlight lang="c">#include <stdio.h>


int max (int *a, int n, int i, int j, int k) {
int max (int *a, int n, int i, int j, int k) {
Line 1,305: Line 1,305:
return 0;
return 0;
}
}
</syntaxhighlight>
</lang>


=={{header|C sharp|C#}}==
=={{header|C sharp|C#}}==
<lang csharp>using System;
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Collections.Generic;
using System.Text;
using System.Text;
Line 1,383: Line 1,383:
HeapSort(s, 0, s.Length, StringComparer.CurrentCultureIgnoreCase);
HeapSort(s, 0, s.Length, StringComparer.CurrentCultureIgnoreCase);
}
}
}</lang>
}</syntaxhighlight>


=={{header|C++}}==
=={{header|C++}}==
Uses C++11. Compile with
Uses C++11. Compile with
g++ -std=c++11 heap.cpp
g++ -std=c++11 heap.cpp
<lang cpp>#include <algorithm>
<syntaxhighlight lang="cpp">#include <algorithm>
#include <iterator>
#include <iterator>
#include <iostream>
#include <iostream>
Line 1,403: Line 1,403:
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));
std::cout << "\n";
std::cout << "\n";
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,412: Line 1,412:
Uses C++11. Compile with
Uses C++11. Compile with
g++ -std=c++11
g++ -std=c++11
<lang cpp>
<syntaxhighlight lang="cpp">
#include <iostream>
#include <iostream>
#include <vector>
#include <vector>
Line 1,459: Line 1,459:
heap_sort(data);
heap_sort(data);
for(int i : data) cout << i << " ";
for(int i : data) cout << i << " ";
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,466: Line 1,466:


=={{header|Clojure}}==
=={{header|Clojure}}==
<lang lisp>(defn- swap [a i j]
<syntaxhighlight lang="lisp">(defn- swap [a i j]
(assoc a i (nth a j) j (nth a i)))
(assoc a i (nth a j) j (nth a i)))
Line 1,493: Line 1,493:
([a]
([a]
(heap-sort a <)))
(heap-sort a <)))
</syntaxhighlight>
</lang>
Example usage:
Example usage:
<lang lisp>user> (heapsort [1 2 4 6 2 3 6])
<syntaxhighlight lang="lisp">user> (heapsort [1 2 4 6 2 3 6])
[1 2 2 3 4 6 6]
[1 2 2 3 4 6 6]
user> (heapsort [1 2 4 6 2 3 6] >)
user> (heapsort [1 2 4 6 2 3 6] >)
[6 6 4 3 2 2 1]
[6 6 4 3 2 2 1]
user> (heapsort (list 1 2 4 6 2 3 6))
user> (heapsort (list 1 2 4 6 2 3 6))
[1 2 2 3 4 6 6]</lang>
[1 2 2 3 4 6 6]</syntaxhighlight>


=={{header|CLU}}==
=={{header|CLU}}==
<lang clu>% Sort an array in place using heap-sort. The contained type
<syntaxhighlight lang="clu">% Sort an array in place using heap-sort. The contained type
% may be any type that can be compared.
% may be any type that can be compared.
heapsort = cluster [T: type] is sort
heapsort = cluster [T: type] is sort
Line 1,584: Line 1,584:
stream$puts(po, "After sorting: ")
stream$puts(po, "After sorting: ")
print_arr[int](po,arr,5)
print_arr[int](po,arr,5)
end start_up</lang>
end start_up</syntaxhighlight>
{{out}}
{{out}}
<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17
<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17
Line 1,591: Line 1,591:
=={{header|COBOL}}==
=={{header|COBOL}}==
{{works with|GnuCOBOL}}
{{works with|GnuCOBOL}}
<lang cobol> >>SOURCE FORMAT FREE
<syntaxhighlight lang="cobol"> >>SOURCE FORMAT FREE
*> This code is dedicated to the public domain
*> This code is dedicated to the public domain
*> This is GNUCOBOL 2.0
*> This is GNUCOBOL 2.0
Line 1,671: Line 1,671:
end-perform
end-perform
.
.
end program heapsort.</lang>
end program heapsort.</syntaxhighlight>
{{out}}
{{out}}
<pre>prompt$ cobc -xj heapsort.cob
<pre>prompt$ cobc -xj heapsort.cob
Line 1,679: Line 1,679:


=={{header|CoffeeScript}}==
=={{header|CoffeeScript}}==
<lang coffeescript># Do an in-place heap sort.
<syntaxhighlight lang="coffeescript"># Do an in-place heap sort.
heap_sort = (arr) ->
heap_sort = (arr) ->
put_array_in_heap_order(arr)
put_array_in_heap_order(arr)
Line 1,711: Line 1,711:
arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
heap_sort arr
heap_sort arr
console.log arr</lang>
console.log arr</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 1,719: Line 1,719:


=={{header|Common Lisp}}==
=={{header|Common Lisp}}==
<lang lisp>(defun make-heap (&optional (length 7))
<syntaxhighlight lang="lisp">(defun make-heap (&optional (length 7))
(make-array length :adjustable t :fill-pointer 0))
(make-array length :adjustable t :fill-pointer 0))


Line 1,791: Line 1,791:
(let ((h (make-heap (length sequence))))
(let ((h (make-heap (length sequence))))
(map nil #'(lambda (e) (heap-insert h e predicate)) sequence)
(map nil #'(lambda (e) (heap-insert h e predicate)) sequence)
(map-into sequence #'(lambda () (heap-delete-min h predicate)))))</lang>
(map-into sequence #'(lambda () (heap-delete-min h predicate)))))</syntaxhighlight>
Example usage:
Example usage:
<pre>(heapsort (vector 1 9 2 8 3 7 4 6 5) '<) ; #(1 2 3 4 5 6 7 8 9)
<pre>(heapsort (vector 1 9 2 8 3 7 4 6 5) '<) ; #(1 2 3 4 5 6 7 8 9)
Line 1,797: Line 1,797:


=={{header|D}}==
=={{header|D}}==
<lang d>import std.stdio, std.container;
<syntaxhighlight lang="d">import std.stdio, std.container;


void heapSort(T)(T[] data) /*pure nothrow @safe @nogc*/ {
void heapSort(T)(T[] data) /*pure nothrow @safe @nogc*/ {
Line 1,807: Line 1,807:
items.heapSort;
items.heapSort;
items.writeln;
items.writeln;
}</lang>
}</syntaxhighlight>


A lower level implementation:
A lower level implementation:
<lang d>import std.stdio, std.algorithm;
<syntaxhighlight lang="d">import std.stdio, std.algorithm;


void heapSort(R)(R seq) pure nothrow @safe @nogc {
void heapSort(R)(R seq) pure nothrow @safe @nogc {
Line 1,841: Line 1,841:
data.heapSort;
data.heapSort;
data.writeln;
data.writeln;
}</lang>
}</syntaxhighlight>


=={{header|Dart}}==
=={{header|Dart}}==
<lang dart>
<syntaxhighlight lang="dart">
void heapSort(List a) {
void heapSort(List a) {
int count = a.length;
int count = a.length;
Line 1,915: Line 1,915:
}
}


</syntaxhighlight>
</lang>
=={{header|Delphi}}==
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Pascal Pascal].
See [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Pascal Pascal].


=={{header|Draco}}==
=={{header|Draco}}==
<lang draco>proc nonrec siftDown([*] int a; word start, end) void:
<syntaxhighlight lang="draco">proc nonrec siftDown([*] int a; word start, end) void:
word root, child;
word root, child;
int temp;
int temp;
Line 1,985: Line 1,985:
write("After sorting: ");
write("After sorting: ");
for i from 0 upto 9 do write(a[i]:5) od
for i from 0 upto 9 do write(a[i]:5) od
corp</lang>
corp</syntaxhighlight>
{{out}}
{{out}}
<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17
<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17
Line 1,992: Line 1,992:
=={{header|E}}==
=={{header|E}}==
{{trans|Python}}
{{trans|Python}}
<lang e>def heapsort := {
<syntaxhighlight lang="e">def heapsort := {
def cswap(c, a, b) {
def cswap(c, a, b) {
def t := c[a]
def t := c[a]
Line 2,028: Line 2,028:
}
}
}
}
}</lang>
}</syntaxhighlight>


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


<lang>subr make_heap
<syntaxhighlight lang="text">subr make_heap
for i = 1 to n - 1
for i = 1 to n - 1
if data[i] > data[(i - 1) / 2]
if data[i] > data[(i - 1) / 2]
Line 2,064: Line 2,064:
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
call sort
call sort
print data[]</lang>
print data[]</syntaxhighlight>


=={{header|EchoLisp}}==
=={{header|EchoLisp}}==
We use the heap library and the '''heap-pop''' primitive to implement heap-sort.
We use the heap library and the '''heap-pop''' primitive to implement heap-sort.
<lang scheme>
<syntaxhighlight lang="scheme">
(lib 'heap)
(lib 'heap)


Line 2,083: Line 2,083:
→ (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)
→ (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14)


</syntaxhighlight>
</lang>


=={{header|Eiffel}}==
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
class
HEAPSORT
HEAPSORT
Line 2,168: Line 2,168:


end
end
</syntaxhighlight>
</lang>
Test:
Test:
<syntaxhighlight lang="eiffel">
<lang Eiffel>
class
class
APPLICATION
APPLICATION
Line 2,205: Line 2,205:


end
end
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 2,213: Line 2,213:


=={{header|Elixir}}==
=={{header|Elixir}}==
<lang elixir>defmodule Sort do
<syntaxhighlight lang="elixir">defmodule Sort do
def heapSort(list) do
def heapSort(list) do
len = length(list)
len = length(list)
Line 2,249: Line 2,249:
end
end


(for _ <- 1..20, do: :rand.uniform(20)) |> IO.inspect |> Sort.heapSort |> IO.inspect</lang>
(for _ <- 1..20, do: :rand.uniform(20)) |> IO.inspect |> Sort.heapSort |> IO.inspect</syntaxhighlight>


{{out}}
{{out}}
Line 2,258: Line 2,258:


=={{header|F Sharp|F#}}==
=={{header|F Sharp|F#}}==
<lang fsharp>let inline swap (a: _ []) i j =
<syntaxhighlight lang="fsharp">let inline swap (a: _ []) i j =
let temp = a.[i]
let temp = a.[i]
a.[i] <- a.[j]
a.[i] <- a.[j]
Line 2,279: Line 2,279:
for term = n - 1 downto 1 do
for term = n - 1 downto 1 do
swap a term 0
swap a term 0
sift cmp a 0 term</lang>
sift cmp a 0 term</syntaxhighlight>


=={{header|Forth}}==
=={{header|Forth}}==
This program assumes that return addresses simply reside as a single cell on the Return Stack. Most Forth compilers fulfill this requirement.
This program assumes that return addresses simply reside as a single cell on the Return Stack. Most Forth compilers fulfill this requirement.
<lang forth>create example
<syntaxhighlight lang="forth">create example
70 , 61 , 63 , 37 , 63 , 25 , 46 , 92 , 38 , 87 ,
70 , 61 , 63 , 37 , 63 , 25 , 46 , 92 , 38 , 87 ,


Line 2,333: Line 2,333:
: .array 10 0 do example i cells + ? loop cr ;
: .array 10 0 do example i cells + ? loop cr ;


.array example 10 heapsort .array </lang>
.array example 10 heapsort .array </syntaxhighlight>




<lang forth>
<syntaxhighlight lang="forth">
\ Written in ANS-Forth; tested under VFX.
\ Written in ANS-Forth; tested under VFX.
\ Requires the novice package: http://www.forth.org/novice.html
\ Requires the novice package: http://www.forth.org/novice.html
Line 2,420: Line 2,420:


10 test-sort
10 test-sort
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre style="height:8ex;overflow:scroll">
<pre style="height:8ex;overflow:scroll">
Line 2,430: Line 2,430:
{{works with|Fortran|90 and later}}
{{works with|Fortran|90 and later}}
Translation of the pseudocode
Translation of the pseudocode
<lang fortran>program Heapsort_Demo
<syntaxhighlight lang="fortran">program Heapsort_Demo
implicit none
implicit none
Line 2,494: Line 2,494:
end subroutine siftdown
end subroutine siftdown


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


=={{header|FreeBASIC}}==
=={{header|FreeBASIC}}==
<lang freebasic>' version 22-10-2016
<syntaxhighlight lang="freebasic">' version 22-10-2016
' compile with: fbc -s console
' compile with: fbc -s console
' for boundary checks on array's compile with: fbc -s console -exx
' for boundary checks on array's compile with: fbc -s console -exx
Line 2,567: Line 2,567:
Print : Print "hit any key to end program"
Print : Print "hit any key to end program"
Sleep
Sleep
End</lang>
End</syntaxhighlight>
{{out}}
{{out}}
<pre>Unsorted
<pre>Unsorted
Line 2,578: Line 2,578:
Direct translation of the pseudocode. The array object (using Scala's <code>ArraySeq</code> class) has built-in method <code>length</code>, so the <code>count</code> parameter is not needed.
Direct translation of the pseudocode. The array object (using Scala's <code>ArraySeq</code> class) has built-in method <code>length</code>, so the <code>count</code> parameter is not needed.


<lang funl>def heapSort( a ) =
<syntaxhighlight lang="funl">def heapSort( a ) =
heapify( a )
heapify( a )
end = a.length() - 1
end = a.length() - 1
Line 2,607: Line 2,607:
a = array( [7, 2, 6, 1, 9, 5, 0, 3, 8, 4] )
a = array( [7, 2, 6, 1, 9, 5, 0, 3, 8, 4] )
heapSort( a )
heapSort( a )
println( a )</lang>
println( a )</syntaxhighlight>


{{out}}
{{out}}
Line 2,619: Line 2,619:


Since we want to implement a generic algorithm, we accept an argument of type <code>sort.Interface</code>, and thus do not have access to the actual elements of the container we're sorting. We can only swap elements. This causes a problem for us when implementing the <code>Pop</code> method, as we can't actually return an element. The ingenious step is realizing that <code>heap.Pop()</code> must move the value to pop to the "end" of the heap area, because its interface only has access to a "Swap" function, and a "Pop" function that pops from the end. (It does not have the ability to pop a value at the beginning.) This is perfect because we precisely want to move the thing popped to the end and shrink the "heap area" by 1. Our "Pop" function returns nothing since we can't get the value, but don't actually need it. (We only need the swapping that it does for us.)
Since we want to implement a generic algorithm, we accept an argument of type <code>sort.Interface</code>, and thus do not have access to the actual elements of the container we're sorting. We can only swap elements. This causes a problem for us when implementing the <code>Pop</code> method, as we can't actually return an element. The ingenious step is realizing that <code>heap.Pop()</code> must move the value to pop to the "end" of the heap area, because its interface only has access to a "Swap" function, and a "Pop" function that pops from the end. (It does not have the ability to pop a value at the beginning.) This is perfect because we precisely want to move the thing popped to the end and shrink the "heap area" by 1. Our "Pop" function returns nothing since we can't get the value, but don't actually need it. (We only need the swapping that it does for us.)
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 2,656: Line 2,656:
heapSort(sort.IntSlice(a))
heapSort(sort.IntSlice(a))
fmt.Println("after: ", a)
fmt.Println("after: ", a)
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 2,663: Line 2,663:
</pre>
</pre>
If you want to implement it manually:
If you want to implement it manually:
<lang go>package main
<syntaxhighlight lang="go">package main


import (
import (
Line 2,700: Line 2,700:
root = child
root = child
}
}
}</lang>
}</syntaxhighlight>


=={{header|Groovy}}==
=={{header|Groovy}}==
Loose translation of the pseudocode:
Loose translation of the pseudocode:
<lang groovy>def makeSwap = { a, i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }
<syntaxhighlight lang="groovy">def makeSwap = { a, i, j = i+1 -> print "."; a[[j,i]] = a[[i,j]] }


def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }
Line 2,728: Line 2,728:
}
}
list
list
}</lang>
}</syntaxhighlight>
Test:
Test:
<lang groovy>println (heapSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
<syntaxhighlight lang="groovy">println (heapSort([23,76,99,58,97,57,35,89,51,38,95,92,24,46,31,24,14,12,57,78,4]))
println (heapSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</lang>
println (heapSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))</syntaxhighlight>
{{out}}
{{out}}
<pre>.......................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
<pre>.......................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]
Line 2,738: Line 2,738:
=={{header|Haskell}}==
=={{header|Haskell}}==
Using package [http://hackage.haskell.org/package/fgl fgl] from HackageDB
Using package [http://hackage.haskell.org/package/fgl fgl] from HackageDB
<lang haskell>import Data.Graph.Inductive.Internal.Heap(
<syntaxhighlight lang="haskell">import Data.Graph.Inductive.Internal.Heap(
Heap(..),insert,findMin,deleteMin)
Heap(..),insert,findMin,deleteMin)


Line 2,752: Line 2,752:


heapsort :: Ord a => [a] -> [a]
heapsort :: Ord a => [a] -> [a]
heapsort = (map fst) . toList . build . map (\x->(x,x))</lang>
heapsort = (map fst) . toList . build . map (\x->(x,x))</syntaxhighlight>
e.g.
e.g.
<lang haskell>*Main> heapsort [[6,9],[2,13],[6,8,14,9],[10,7],[5]]
<syntaxhighlight lang="haskell">*Main> heapsort [[6,9],[2,13],[6,8,14,9],[10,7],[5]]
[[2,13],[5],[6,8,14,9],[6,9],[10,7]]</lang>
[[2,13],[5],[6,8,14,9],[6,9],[10,7]]</syntaxhighlight>


=={{header|Haxe}}==
=={{header|Haxe}}==
{{trans|D}}
{{trans|D}}
<lang haxe>class HeapSort {
<syntaxhighlight lang="haxe">class HeapSort {
@:generic
@:generic
private static function siftDown<T>(arr: Array<T>, start:Int, end:Int) {
private static function siftDown<T>(arr: Array<T>, start:Int, end:Int) {
Line 2,818: Line 2,818:
Sys.println('Sorted Strings: ' + stringArray);
Sys.println('Sorted Strings: ' + stringArray);
}
}
}</lang>
}</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 2,830: Line 2,830:


=={{header|Icon}} and {{header|Unicon}}==
=={{header|Icon}} and {{header|Unicon}}==
<lang Icon>procedure main() #: demonstrate various ways to sort a list and string
<syntaxhighlight lang="icon">procedure main() #: demonstrate various ways to sort a list and string
demosort(heapsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
demosort(heapsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
end
Line 2,866: Line 2,866:
}
}
return X
return X
end</lang>
end</syntaxhighlight>
Algorithm notes:
Algorithm notes:
* This is a fairly straight forward implementation of the pseudo-code with 'heapify' coded in-line.
* This is a fairly straight forward implementation of the pseudo-code with 'heapify' coded in-line.
Line 2,886: Line 2,886:
{{eff note|J|/:~}}
{{eff note|J|/:~}}
'''Translation of the pseudocode'''
'''Translation of the pseudocode'''
<lang j>swap=: C.~ <
<syntaxhighlight lang="j">swap=: C.~ <


siftDown=: 4 : 0
siftDown=: 4 : 0
Line 2,902: Line 2,902:
z=. siftDown&.>/ (c,~each i.<.c%2),<y NB. heapify
z=. siftDown&.>/ (c,~each i.<.c%2),<y NB. heapify
> ([ siftDown swap~)&.>/ (0,each}.i.c),z
> ([ siftDown swap~)&.>/ (0,each}.i.c),z
)</lang>
)</syntaxhighlight>
'''Examples'''
'''Examples'''
<lang j> heapSort 1 5 2 7 3 9 4 6 8 1
<syntaxhighlight lang="j"> heapSort 1 5 2 7 3 9 4 6 8 1
1 1 2 3 4 5 6 7 8 9
1 1 2 3 4 5 6 7 8 9


heapSort &. (a.&i.) 'aqwcdhkij'
heapSort &. (a.&i.) 'aqwcdhkij'
acdhijkqw</lang>
acdhijkqw</syntaxhighlight>


=={{header|Janet}}==
=={{header|Janet}}==
Line 2,915: Line 2,915:
Although Janet is a (functional) Lisp, it has support for [https://janet-lang.org/docs/data_structures/arrays.html mutable arrays] and imperative programming.
Although Janet is a (functional) Lisp, it has support for [https://janet-lang.org/docs/data_structures/arrays.html mutable arrays] and imperative programming.


<lang janet>
<syntaxhighlight lang="janet">
(defn swap [l a b]
(defn swap [l a b]
(let [aval (get l a) bval (get l b)]
(let [aval (get l a) bval (get l b)]
Line 3,002: Line 3,002:


# NOTE: Makes a copy of input array. Output is mutable
# NOTE: Makes a copy of input array. Output is mutable
(print (heap-sort [7 12 3 9 -1 17 6]))</lang>
(print (heap-sort [7 12 3 9 -1 17 6]))</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 3,010: Line 3,010:
=={{header|Java}}==
=={{header|Java}}==
Direct translation of the pseudocode.
Direct translation of the pseudocode.
<lang java>public static void heapSort(int[] a){
<syntaxhighlight lang="java">public static void heapSort(int[] a){
int count = a.length;
int count = a.length;


Line 3,062: Line 3,062:
return;
return;
}
}
}</lang>
}</syntaxhighlight>


=={{header|Javascript}}==
=={{header|Javascript}}==
<syntaxhighlight lang="javascript">
<lang Javascript>
function heapSort(arr) {
function heapSort(arr) {
heapify(arr)
heapify(arr)
Line 3,105: Line 3,105:
heapSort(arr)
heapSort(arr)
expect(arr).toStrictEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
expect(arr).toStrictEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
})</lang>
})</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 3,116: Line 3,116:


Since jq is a purely functional language, the putative benefits of the heapsort algorithm do not accrue here.
Since jq is a purely functional language, the putative benefits of the heapsort algorithm do not accrue here.
<lang jq>def swap($a; $i; $j):
<syntaxhighlight lang="jq">def swap($a; $i; $j):
$a
$a
| .[$i] as $t
| .[$i] as $t
Line 3,159: Line 3,159:
"Before: \(.)",
"Before: \(.)",
"After : \(heapSort)\n"
"After : \(heapSort)\n"
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 3,170: Line 3,170:


=={{header|Julia}}==
=={{header|Julia}}==
<lang julia>function swap(a, i, j)
<syntaxhighlight lang="julia">function swap(a, i, j)
a[i], a[j] = a[j], a[i]
a[i], a[j] = a[j], a[i]
end
end
Line 3,212: Line 3,212:
println("Unsorted: $a")
println("Unsorted: $a")
println("Heap sorted: ", heapsort!(a))
println("Heap sorted: ", heapsort!(a))
</lang>{{output}}<pre>
</syntaxhighlight>{{output}}<pre>
Unsorted: [3, 12, 11, 4, 2, 7, 5, 8, 9, 1, 10, 6]
Unsorted: [3, 12, 11, 4, 2, 7, 5, 8, 9, 1, 10, 6]
Heap sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Heap sorted: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
Line 3,218: Line 3,218:


=={{header|Kotlin}}==
=={{header|Kotlin}}==
<lang scala>// version 1.1.0
<syntaxhighlight lang="scala">// version 1.1.0


fun heapSort(a: IntArray) {
fun heapSort(a: IntArray) {
Line 3,265: Line 3,265:
println(a.joinToString(", "))
println(a.joinToString(", "))
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 3,275: Line 3,275:


=={{header|Liberty BASIC}}==
=={{header|Liberty BASIC}}==
<lang lb>wikiSample=1 'comment out for random array
<syntaxhighlight lang="lb">wikiSample=1 'comment out for random array


data 6, 5, 3, 1, 8, 7, 2, 4
data 6, 5, 3, 1, 8, 7, 2, 4
Line 3,352: Line 3,352:
next i
next i
print
print
end sub</lang>
end sub</syntaxhighlight>


=={{header|Lobster}}==
=={{header|Lobster}}==
<lang Lobster>def siftDown(a, start, end):
<syntaxhighlight lang="lobster">def siftDown(a, start, end):
// (end represents the limit of how far down the heap to sift)
// (end represents the limit of how far down the heap to sift)
var root = start
var root = start
Line 3,412: Line 3,412:
heapSort(inputs)
heapSort(inputs)
print ("sorted: " + inputs)
print ("sorted: " + inputs)
</syntaxhighlight>
</lang>
{{out}}
{{out}}
<pre>
<pre>
Line 3,425: Line 3,425:
=={{header|LotusScript}}==
=={{header|LotusScript}}==


<syntaxhighlight lang="lotusscript">
<lang LotusScript>
Public Sub heapsort(pavIn As Variant)
Public Sub heapsort(pavIn As Variant)
Dim liCount As Integer, liEnd As Integer
Dim liCount As Integer, liEnd As Integer
Line 3,471: Line 3,471:
wend
wend
End Sub
End Sub
</syntaxhighlight>
</lang>


=={{header|M4}}==
=={{header|M4}}==
<lang M4>divert(-1)
<syntaxhighlight lang="m4">divert(-1)


define(`randSeed',141592653)
define(`randSeed',141592653)
Line 3,529: Line 3,529:
show(`a')
show(`a')
heapsort(`a')
heapsort(`a')
show(`a')</lang>
show(`a')</syntaxhighlight>


=={{header|Maple}}==
=={{header|Maple}}==
<lang>swap := proc(arr, a, b)
<syntaxhighlight lang="text">swap := proc(arr, a, b)
local temp:
local temp:
temp := arr[a]:
temp := arr[a]:
Line 3,567: Line 3,567:
arr := Array([17,3,72,0,36,2,3,8,40,0]);
arr := Array([17,3,72,0,36,2,3,8,40,0]);
heapsort(arr);
heapsort(arr);
arr;</lang>
arr;</syntaxhighlight>
{{Out|Output}}
{{Out|Output}}
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>


=={{header|Mathematica}}/{{header|Wolfram Language}}==
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<lang Mathematica>siftDown[list_,root_,theEnd_]:=
<syntaxhighlight lang="mathematica">siftDown[list_,root_,theEnd_]:=
While[(root*2) <= theEnd,
While[(root*2) <= theEnd,
child = root*2;
child = root*2;
Line 3,589: Line 3,589:
count--; list = siftDown[list,1,count];
count--; list = siftDown[list,1,count];
]
]
]</lang>
]</syntaxhighlight>
{{out}}
{{out}}
<pre>heapSort@{2,3,1,5,7,6}
<pre>heapSort@{2,3,1,5,7,6}
Line 3,596: Line 3,596:
=={{header|MATLAB}} / {{header|Octave}}==
=={{header|MATLAB}} / {{header|Octave}}==
This function definition is an almost exact translation of the pseudo-code into MATLAB, but I have chosen to make the heapify function inline because it is only called once in the pseudo-code. Also, MATLAB uses 1 based array indecies, therefore all of the pseudo-code has been translated to reflect that difference.
This function definition is an almost exact translation of the pseudo-code into MATLAB, but I have chosen to make the heapify function inline because it is only called once in the pseudo-code. Also, MATLAB uses 1 based array indecies, therefore all of the pseudo-code has been translated to reflect that difference.
<lang MATLAB>function list = heapSort(list)
<syntaxhighlight lang="matlab">function list = heapSort(list)


function list = siftDown(list,root,theEnd)
function list = siftDown(list,root,theEnd)
Line 3,635: Line 3,635:
end
end
end</lang>
end</syntaxhighlight>
Sample Usage:
Sample Usage:
<lang MATLAB>>> heapSort([4 3 1 5 6 2])
<syntaxhighlight lang="matlab">>> heapSort([4 3 1 5 6 2])


ans =
ans =


1 2 3 4 5 6</lang>
1 2 3 4 5 6</syntaxhighlight>


=={{header|MAXScript}}==
=={{header|MAXScript}}==
<lang MAXScript>fn heapify arr count =
<syntaxhighlight lang="maxscript">fn heapify arr count =
(
(
local s = count /2
local s = count /2
Line 3,686: Line 3,686:
)
)
)</lang>
)</syntaxhighlight>
Output:
Output:
<syntaxhighlight lang="maxscript">
<lang MAXScript>
a = for i in 1 to 10 collect random 0 9
a = for i in 1 to 10 collect random 0 9
#(7, 2, 5, 6, 1, 5, 4, 0, 1, 6)
#(7, 2, 5, 6, 1, 5, 4, 0, 1, 6)
heapSort a
heapSort a
#(0, 1, 1, 2, 4, 5, 5, 6, 6, 7)
#(0, 1, 1, 2, 4, 5, 5, 6, 6, 7)
</syntaxhighlight>
</lang>


=={{header|Mercury}}==
=={{header|Mercury}}==
Line 3,699: Line 3,699:




<lang mercury>%%%-------------------------------------------------------------------
<syntaxhighlight lang="mercury">%%%-------------------------------------------------------------------


:- module heapsort_task.
:- module heapsort_task.
Line 3,804: Line 3,804:
%%% mode: mercury
%%% mode: mercury
%%% prolog-indent-width: 2
%%% prolog-indent-width: 2
%%% end:</lang>
%%% end:</syntaxhighlight>


{{out}}
{{out}}
Line 3,813: Line 3,813:


=={{header|NetRexx}}==
=={{header|NetRexx}}==
<lang NetRexx>/* NetRexx */
<syntaxhighlight lang="netrexx">/* NetRexx */
options replace format comments java crossref savelog symbols binary
options replace format comments java crossref savelog symbols binary


Line 3,895: Line 3,895:
end root
end root


return a</lang>
return a</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 3,918: Line 3,918:


=={{header|Nim}}==
=={{header|Nim}}==
<lang nim>proc siftDown[T](a: var openarray[T]; start, ending: int) =
<syntaxhighlight lang="nim">proc siftDown[T](a: var openarray[T]; start, ending: int) =
var root = start
var root = start
while root * 2 + 1 < ending:
while root * 2 + 1 < ending:
Line 3,940: Line 3,940:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
heapSort a
heapSort a
echo a</lang>
echo a</syntaxhighlight>
{{out}}
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
Line 3,946: Line 3,946:
=={{header|Objeck}}==
=={{header|Objeck}}==
{{trans|Java}}
{{trans|Java}}
<lang objeck>bundle Default {
<syntaxhighlight lang="objeck">bundle Default {
class HeapSort {
class HeapSort {
function : Main(args : String[]) ~ Nil {
function : Main(args : String[]) ~ Nil {
Line 3,998: Line 3,998:
}
}
}
}
}</lang>
}</syntaxhighlight>


=={{header|OCaml}}==
=={{header|OCaml}}==
<lang ocaml>let heapsort a =
<syntaxhighlight lang="ocaml">let heapsort a =


let swap i j =
let swap i j =
Line 4,023: Line 4,023:
swap term 0;
swap term 0;
sift 0 term;
sift 0 term;
done;;</lang>
done;;</syntaxhighlight>
Usage:
Usage:
<lang ocaml>let a = [|3;1;4;1;5;9;2;6;5;3;5;8;97;93;23;84;62;64;33;83;27;95|] in
<syntaxhighlight lang="ocaml">let a = [|3;1;4;1;5;9;2;6;5;3;5;8;97;93;23;84;62;64;33;83;27;95|] in
heapsort a;
heapsort a;
Array.iter (Printf.printf "%d ") a;;
Array.iter (Printf.printf "%d ") a;;
Line 4,034: Line 4,034:
heapsort b;
heapsort b;
Array.iter print_char b;;
Array.iter print_char b;;
print_newline ();;</lang>
print_newline ();;</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,043: Line 4,043:
=={{header|Oz}}==
=={{header|Oz}}==
A faithful translation of the pseudocode, adjusted to the fact that Oz arrays can start with an arbitrary index, not just 0 or 1.
A faithful translation of the pseudocode, adjusted to the fact that Oz arrays can start with an arbitrary index, not just 0 or 1.
<lang oz>declare
<syntaxhighlight lang="oz">declare
proc {HeapSort A}
proc {HeapSort A}
Low = {Array.low A}
Low = {Array.low A}
Line 4,099: Line 4,099:
in
in
{HeapSort Arr}
{HeapSort Arr}
{Show {Array.toRecord unit Arr}}</lang>
{Show {Array.toRecord unit Arr}}</syntaxhighlight>


=={{header|Pascal}}==
=={{header|Pascal}}==
An example, which works on arrays with arbitrary bounds :-)
An example, which works on arrays with arbitrary bounds :-)
<lang pascal>program HeapSortDemo;
<syntaxhighlight lang="pascal">program HeapSortDemo;


type
type
Line 4,179: Line 4,179:
end;
end;
writeln;
writeln;
end.</lang>
end.</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,189: Line 4,189:


=={{header|Perl}}==
=={{header|Perl}}==
<lang perl>#!/usr/bin/perl
<syntaxhighlight lang="perl">#!/usr/bin/perl


my @a = (4, 65, 2, -31, 0, 99, 2, 83, 782, 1);
my @a = (4, 65, 2, -31, 0, 99, 2, 83, 782, 1);
Line 4,229: Line 4,229:
return $m;
return $m;
}
}
</syntaxhighlight>
</lang>


=={{header|Phix}}==
=={{header|Phix}}==
<!--<lang Phix>(phixonline)-->
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 4,274: Line 4,274:
<span style="color: #0000FF;">?</span><span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"oranges"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"and"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"apples"</span><span style="color: #0000FF;">})</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">heap_sort</span><span style="color: #0000FF;">({</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"oranges"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"and"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"apples"</span><span style="color: #0000FF;">})</span>
<!--</lang>-->
<!--</syntaxhighlight>-->
{{out}}
{{out}}
<pre>
<pre>
Line 4,281: Line 4,281:


=={{header|Picat}}==
=={{header|Picat}}==
<lang Picat>main =>
<syntaxhighlight lang="picat">main =>
_ = random2(),
_ = random2(),
A = [random(-10,10) : _ in 1..30],
A = [random(-10,10) : _ in 1..30],
Line 4,324: Line 4,324:
T = L[I],
T = L[I],
L[I] := L[J],
L[I] := L[J],
L[J] := T.</lang>
L[J] := T.</syntaxhighlight>


{{out}}
{{out}}
Line 4,332: Line 4,332:


=={{header|PicoLisp}}==
=={{header|PicoLisp}}==
<lang PicoLisp>(de heapSort (A Cnt)
<syntaxhighlight lang="picolisp">(de heapSort (A Cnt)
(let Cnt (length A)
(let Cnt (length A)
(for (Start (/ Cnt 2) (gt0 Start) (dec Start))
(for (Start (/ Cnt 2) (gt0 Start) (dec Start))
Line 4,350: Line 4,350:
(NIL (> (get A Child) (get A Root)))
(NIL (> (get A Child) (get A Root)))
(xchg (nth A Root) (nth A Child))
(xchg (nth A Root) (nth A Child))
(setq Root Child) ) ) )</lang>
(setq Root Child) ) ) )</syntaxhighlight>
{{out}}
{{out}}
<pre>: (heapSort (make (do 9 (link (rand 1 999)))))
<pre>: (heapSort (make (do 9 (link (rand 1 999)))))
Line 4,356: Line 4,356:


=={{header|PL/I}}==
=={{header|PL/I}}==
<lang pli>*process source xref attributes or(!);
<syntaxhighlight lang="pli">*process source xref attributes or(!);
/*********************************************************************
/*********************************************************************
* Pseudocode found here:
* Pseudocode found here:
Line 4,431: Line 4,431:
End;
End;


End;</lang>
End;</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,489: Line 4,489:


=={{header|PL/M}}==
=={{header|PL/M}}==
<lang plm>100H:
<syntaxhighlight lang="plm">100H:


/* HEAP SORT AN ARRAY OF 16-BIT INTEGERS */
/* HEAP SORT AN ARRAY OF 16-BIT INTEGERS */
Line 4,563: Line 4,563:


CALL BDOS(0,0);
CALL BDOS(0,0);
EOF</lang>
EOF</syntaxhighlight>
{{out}}
{{out}}
<pre>0 1 2 2 3 4 8 31 65 99 782</pre>
<pre>0 1 2 2 3 4 8 31 65 99 782</pre>


=={{header|PowerShell}}==
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
<lang PowerShell>
function heapsort($a, $count) {
function heapsort($a, $count) {
$a = heapify $a $count
$a = heapify $a $count
Line 4,604: Line 4,604:
$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)
$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)
"$(heapsort $array $array.Count)"
"$(heapsort $array $array.Count)"
</syntaxhighlight>
</lang>
<b>Output:</b>
<b>Output:</b>
<pre>
<pre>
Line 4,611: Line 4,611:


=={{header|PureBasic}}==
=={{header|PureBasic}}==
<lang PureBasic>Declare heapify(Array a(1), count)
<syntaxhighlight lang="purebasic">Declare heapify(Array a(1), count)
Declare siftDown(Array a(1), start, ending)
Declare siftDown(Array a(1), start, ending)


Line 4,646: Line 4,646:
EndIf
EndIf
Wend
Wend
EndProcedure</lang>
EndProcedure</syntaxhighlight>


=={{header|Python}}==
=={{header|Python}}==
<lang python>def heapsort(lst):
<syntaxhighlight lang="python">def heapsort(lst):
''' Heapsort. Note: this function sorts in-place (it mutates the list). '''
''' Heapsort. Note: this function sorts in-place (it mutates the list). '''


Line 4,672: Line 4,672:
root = child
root = child
else:
else:
break</lang>
break</syntaxhighlight>
Testing:
Testing:
<pre>>>> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
<pre>>>> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
Line 4,682: Line 4,682:
This uses code from [[Priority queue#Quackery]].
This uses code from [[Priority queue#Quackery]].


<lang Quackery> [ [] swap pqwith >
<syntaxhighlight lang="quackery"> [ [] swap pqwith >
dup pqsize times
dup pqsize times
[ frompq rot join swap ]
[ frompq rot join swap ]
Line 4,689: Line 4,689:
[] 23 times [ 90 random 10 + join ]
[] 23 times [ 90 random 10 + join ]
say " " dup echo cr
say " " dup echo cr
say " --> " hsort echo </lang>
say " --> " hsort echo </syntaxhighlight>


''' Output:'''
''' Output:'''
Line 4,696: Line 4,696:


=={{header|Racket}}==
=={{header|Racket}}==
<lang racket>
<syntaxhighlight lang="racket">
#lang racket
#lang racket
(require (only-in srfi/43 vector-swap!))
(require (only-in srfi/43 vector-swap!))
Line 4,723: Line 4,723:
(sift-down! 0 (- end 1)))
(sift-down! 0 (- end 1)))
xs)
xs)
</syntaxhighlight>
</lang>


=={{header|Raku}}==
=={{header|Raku}}==
(formerly Perl 6)
(formerly Perl 6)
<lang perl6>sub heap_sort ( @list ) {
<syntaxhighlight lang="raku" line>sub heap_sort ( @list ) {
for ( 0 ..^ +@list div 2 ).reverse -> $start {
for ( 0 ..^ +@list div 2 ).reverse -> $start {
_sift_down $start, @list.end, @list;
_sift_down $start, @list.end, @list;
Line 4,751: Line 4,751:
say 'Input = ' ~ @data;
say 'Input = ' ~ @data;
@data.&heap_sort;
@data.&heap_sort;
say 'Output = ' ~ @data;</lang>
say 'Output = ' ~ @data;</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>
Line 4,764: Line 4,764:


Indexing of the array starts with &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.
Indexing of the array starts with &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.
<lang rexx>/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
<syntaxhighlight lang="rexx">/*REXX pgm sorts an array (names of epichoric Greek letters) using a heapsort algorithm.*/
parse arg x; call init /*use args or default, define @ array.*/
parse arg x; call init /*use args or default, define @ array.*/
call show "before sort:" /*#: the number of elements in array*/
call show "before sort:" /*#: the number of elements in array*/
Line 4,785: Line 4,785:
end /*while*/; @.i= $; return /*define lowest.*/
end /*while*/; @.i= $; return /*define lowest.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
/*──────────────────────────────────────────────────────────────────────────────────────*/
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</lang>
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</syntaxhighlight>
{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}
{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}
(Shown at three-quarter size.)
(Shown at three-quarter size.)
Line 4,910: Line 4,910:


===version 2===
===version 2===
<lang rexx>/* REXX ***************************************************************
<syntaxhighlight lang="rexx">/* REXX ***************************************************************
* Translated from PL/I
* Translated from PL/I
* 27.07.2013 Walter Pachl
* 27.07.2013 Walter Pachl
Line 4,981: Line 4,981:
Say 'element' format(j,2) txt a.j
Say 'element' format(j,2) txt a.j
End
End
Return</lang>
Return</syntaxhighlight>
Output: see PL/I
Output: see PL/I


=={{header|Ring}}==
=={{header|Ring}}==
<lang ring>
<syntaxhighlight lang="ring">
# Project : Sorting algorithms/Heapsort
# Project : Sorting algorithms/Heapsort


Line 5,036: Line 5,036:
svect = left(svect, len(svect) - 1)
svect = left(svect, len(svect) - 1)
see svect + nl
see svect + nl
</syntaxhighlight>
</lang>
Output:
Output:
<pre>
<pre>
Line 5,046: Line 5,046:


=={{header|Ruby}}==
=={{header|Ruby}}==
<lang ruby>class Array
<syntaxhighlight lang="ruby">class Array
def heapsort
def heapsort
self.dup.heapsort!
self.dup.heapsort!
Line 5,079: Line 5,079:
end
end
end
end
end</lang>
end</syntaxhighlight>
Testing:
Testing:
<pre>irb(main):035:0> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
<pre>irb(main):035:0> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
Line 5,089: Line 5,089:
{{trans|Python}}
{{trans|Python}}
This program allows the caller to specify an arbitrary function by which an order is determined.
This program allows the caller to specify an arbitrary function by which an order is determined.
<lang rust>fn main() {
<syntaxhighlight lang="rust">fn main() {
let mut v = [4, 6, 8, 1, 0, 3, 2, 2, 9, 5];
let mut v = [4, 6, 8, 1, 0, 3, 2, 2, 9, 5];
heap_sort(&mut v, |x, y| x < y);
heap_sort(&mut v, |x, y| x < y);
Line 5,131: Line 5,131:
}
}
}
}
}</lang>
}</syntaxhighlight>


Of course, you could also simply use <code>BinaryHeap</code> in the standard library.
Of course, you could also simply use <code>BinaryHeap</code> in the standard library.


<lang rust>use std::collections::BinaryHeap;
<syntaxhighlight lang="rust">use std::collections::BinaryHeap;


fn main() {
fn main() {
Line 5,141: Line 5,141:
let sorted = BinaryHeap::from(src).into_sorted_vec();
let sorted = BinaryHeap::from(src).into_sorted_vec();
println!("{:?}", sorted);
println!("{:?}", sorted);
}</lang>
}</syntaxhighlight>


=={{header|Scala}}==
=={{header|Scala}}==
{{works with|Scala|2.8}}
{{works with|Scala|2.8}}
This code is not written for maximum performance, though, of course, it preserves the O(n log n) characteristic of heap sort.
This code is not written for maximum performance, though, of course, it preserves the O(n log n) characteristic of heap sort.
<lang scala>def heapSort[T](a: Array[T])(implicit ord: Ordering[T]) {
<syntaxhighlight lang="scala">def heapSort[T](a: Array[T])(implicit ord: Ordering[T]) {
import scala.annotation.tailrec // Ensure functions are tail-recursive
import scala.annotation.tailrec // Ensure functions are tail-recursive
import ord._
import ord._
Line 5,187: Line 5,187:
siftDown(0, i)
siftDown(0, i)
}
}
}</lang>
}</syntaxhighlight>


=={{header|Scheme}}==
=={{header|Scheme}}==
{{works with|Scheme|R<math>^5</math>RS}}
{{works with|Scheme|R<math>^5</math>RS}}
<lang scheme>; swap two elements of a vector
<syntaxhighlight lang="scheme">; swap two elements of a vector
(define (swap! v i j)
(define (swap! v i j)
(define temp (vector-ref v i))
(define temp (vector-ref v i))
Line 5,244: Line 5,244:
(define uriah (list->vector '(3 5 7 9 0 8 1 4 2 6)))
(define uriah (list->vector '(3 5 7 9 0 8 1 4 2 6)))
(heapsort uriah)
(heapsort uriah)
uriah</lang>
uriah</syntaxhighlight>
{{out}}
{{out}}
<pre>done
<pre>done
Line 5,250: Line 5,250:


=={{header|Seed7}}==
=={{header|Seed7}}==
<lang seed7>const proc: downheap (inout array elemType: arr, in var integer: k, in integer: n) is func
<syntaxhighlight lang="seed7">const proc: downheap (inout array elemType: arr, in var integer: k, in integer: n) is func
local
local
var elemType: help is elemType.value;
var elemType: help is elemType.value;
Line 5,288: Line 5,288:
downheap(arr, 1, n);
downheap(arr, 1, n);
until n <= 1;
until n <= 1;
end func;</lang>
end func;</syntaxhighlight>
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#heapSort]
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#heapSort]


=={{header|SequenceL}}==
=={{header|SequenceL}}==
<syntaxhighlight lang="sequencel">
<lang sequenceL>
import <Utilities/Sequence.sl>;
import <Utilities/Sequence.sl>;


Line 5,325: Line 5,325:
in
in
setElementAt(setElementAt(list, i, vals.B), j, vals.A);
setElementAt(setElementAt(list, i, vals.B), j, vals.A);
</syntaxhighlight>
</lang>


=={{header|Sidef}}==
=={{header|Sidef}}==
<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) {
Line 5,366: Line 5,366:
say arr; # prints the unsorted array
say arr; # prints the unsorted array
heap_sort(arr, arr.len); # sorts the array in-place
heap_sort(arr, arr.len); # sorts the array in-place
say arr; # prints the sorted array</lang>
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]
Line 5,375: Line 5,375:
Since Standard ML is a functional language, a [http://en.wikipedia.org/wiki/Pairing_heap pairing heap] is used instead of a standard binary heap.
Since Standard ML is a functional language, a [http://en.wikipedia.org/wiki/Pairing_heap pairing heap] is used instead of a standard binary heap.


<lang sml>(* Pairing heap - http://en.wikipedia.org/wiki/Pairing_heap *)
<syntaxhighlight lang="sml">(* Pairing heap - http://en.wikipedia.org/wiki/Pairing_heap *)
functor PairingHeap(type t
functor PairingHeap(type t
val cmp : t * t -> order) =
val cmp : t * t -> order) =
Line 5,429: Line 5,429:
val test_3 = heapsort [6,2,7,5,8,1,3,4] = [1, 2, 3, 4, 5, 6, 7, 8]
val test_3 = heapsort [6,2,7,5,8,1,3,4] = [1, 2, 3, 4, 5, 6, 7, 8]
end;
end;
</syntaxhighlight>
</lang>


=={{header|Stata}}==
=={{header|Stata}}==
Line 5,435: Line 5,435:
Variant with siftup and siftdown, using Mata.
Variant with siftup and siftdown, using Mata.


<lang mata>function siftup(a, i) {
<syntaxhighlight lang="mata">function siftup(a, i) {
k = i
k = i
while (k > 1) {
while (k > 1) {
Line 5,478: Line 5,478:
siftdown(a, i-1)
siftdown(a, i-1)
}
}
}</lang>
}</syntaxhighlight>


=={{header|Swift}}==
=={{header|Swift}}==
<lang Swift>func heapsort<T:Comparable>(inout list:[T]) {
<syntaxhighlight lang="swift">func heapsort<T:Comparable>(inout list:[T]) {
var count = list.count
var count = list.count
Line 5,529: Line 5,529:
shiftDown(&list, 0, end)
shiftDown(&list, 0, end)
}
}
}</lang>
}</syntaxhighlight>


=={{header|Tcl}}==
=={{header|Tcl}}==
Based on the algorithm from Wikipedia:
Based on the algorithm from Wikipedia:
{{works with|Tcl|8.5}}
{{works with|Tcl|8.5}}
<lang tcl>package require Tcl 8.5
<syntaxhighlight lang="tcl">package require Tcl 8.5


proc heapsort {list {count ""}} {
proc heapsort {list {count ""}} {
Line 5,572: Line 5,572:
lset a $x [lindex $a $y]
lset a $x [lindex $a $y]
lset a $y $tmp
lset a $y $tmp
}</lang>
}</syntaxhighlight>
Demo code:
Demo code:
<lang tcl>puts [heapsort {1 5 3 7 9 2 8 4 6 0}]</lang>
<syntaxhighlight lang="tcl">puts [heapsort {1 5 3 7 9 2 8 4 6 0}]</syntaxhighlight>
{{out}}
{{out}}
<pre>0 1 2 3 4 5 6 7 8 9</pre>
<pre>0 1 2 3 4 5 6 7 8 9</pre>
Line 5,653: Line 5,653:
=={{header|True BASIC}}==
=={{header|True BASIC}}==
{{trans|Liberty BASIC}}
{{trans|Liberty BASIC}}
<lang qbasic>
<syntaxhighlight lang="qbasic">
!creamos la matriz y la inicializamos
!creamos la matriz y la inicializamos
LET lim = 20
LET lim = 20
Line 5,728: Line 5,728:
CALL printArray (lim)
CALL printArray (lim)
END
END
</syntaxhighlight>
</lang>




=={{header|uBasic/4tH}}==
=={{header|uBasic/4tH}}==
<lang>PRINT "Heap sort:"
<syntaxhighlight lang="text">PRINT "Heap sort:"
n = FUNC (_InitArray)
n = FUNC (_InitArray)
PROC _ShowArray (n)
PROC _ShowArray (n)
Line 5,804: Line 5,804:


PRINT
PRINT
RETURN</lang>
RETURN</syntaxhighlight>


=={{header|Vala}}==
=={{header|Vala}}==
{{trans|C++}}
{{trans|C++}}
<lang vala>void swap(int[] array, int i1, int i2) {
<syntaxhighlight lang="vala">void swap(int[] array, int i1, int i2) {
if (array[i1] == array[i2])
if (array[i1] == array[i2])
return;
return;
Line 5,860: Line 5,860:
stdout.printf("%d ", i);
stdout.printf("%d ", i);
}
}
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 5,869: Line 5,869:
=={{header|VBA}}==
=={{header|VBA}}==
{{trans|FreeBASIC}}
{{trans|FreeBASIC}}
<lang VBA>Sub SiftDown(list() As Integer, start As Long, eend As Long)
<syntaxhighlight lang="vba">Sub SiftDown(list() As Integer, start As Long, eend As Long)
Dim root As Long : root = start
Dim root As Long : root = start
Dim lb As Long : lb = LBound(list)
Dim lb As Long : lb = LBound(list)
Line 5,915: Line 5,915:
SiftDown list(), 0, eend
SiftDown list(), 0, eend
Wend
Wend
End Sub</lang>
End Sub</syntaxhighlight>


=={{header|Wren}}==
=={{header|Wren}}==
<lang ecmascript>var siftDown = Fn.new { |a, start, end|
<syntaxhighlight lang="ecmascript">var siftDown = Fn.new { |a, start, end|
var root = start
var root = start
while (root*2 + 1 <= end) {
while (root*2 + 1 <= end) {
Line 5,961: Line 5,961:
System.print("After : %(a)")
System.print("After : %(a)")
System.print()
System.print()
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 5,974: Line 5,974:
Alternatively, we can just call a library method.
Alternatively, we can just call a library method.
{{libheader|Wren-sort}}
{{libheader|Wren-sort}}
<lang ecmascript>import "/sort" for Sort
<syntaxhighlight lang="ecmascript">import "/sort" for Sort


var as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
var as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]
Line 5,982: Line 5,982:
System.print("After : %(a)")
System.print("After : %(a)")
System.print()
System.print()
}</lang>
}</syntaxhighlight>


{{out}}
{{out}}
Line 5,990: Line 5,990:


=={{header|zkl}}==
=={{header|zkl}}==
<lang zkl>fcn heapSort(a){ // in place
<syntaxhighlight lang="zkl">fcn heapSort(a){ // in place
n := a.len();
n := a.len();
foreach start in ([(n-2)/2 .. 0,-1])
foreach start in ([(n-2)/2 .. 0,-1])
Line 6,008: Line 6,008:
start = child;
start = child;
}
}
}</lang>
}</syntaxhighlight>
<lang zkl>heapSort(L(170, 45, 75, -90, -802, 24, 2, 66)).println();
<syntaxhighlight lang="zkl">heapSort(L(170, 45, 75, -90, -802, 24, 2, 66)).println();
heapSort("this is a test".split("")).println();</lang>
heapSort("this is a test".split("")).println();</syntaxhighlight>
{{out}}
{{out}}
<pre>
<pre>