Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 67: | Line 67: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<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)</ |
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. |
||
< |
<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</ |
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}}== |
||
< |
<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: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
This implementation is a generic heapsort for unconstrained arrays. |
This implementation is a generic heapsort for unconstrained arrays. |
||
< |
<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);</ |
procedure Generic_Heapsort(Item : in out Collection);</syntaxhighlight> |
||
< |
<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;</ |
end Generic_Heapsort;</syntaxhighlight> |
||
Demo code: |
Demo code: |
||
< |
<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;</ |
end Test_Generic_Heapsort;</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<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)) |
||
)</ |
)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 654: | Line 654: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
===Binary heap=== |
===Binary heap=== |
||
< |
<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</ |
return aList</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<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=== |
||
< |
<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</ |
return aList</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<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}}== |
||
< |
<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]</ |
print heapSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,134: | Line 1,134: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<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</ |
MsgBox</syntaxhighlight> |
||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
< |
<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</ |
ENDPROC</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,211: | Line 1,211: | ||
=={{header|BCPL}}== |
=={{header|BCPL}}== |
||
< |
<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() |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<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#}}== |
||
< |
<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); |
||
} |
} |
||
}</ |
}</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 |
||
< |
<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"; |
||
}</ |
}</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 |
||
< |
<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 << " "; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,466: | Line 1,466: | ||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<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: |
||
< |
<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]</ |
[1 2 2 3 4 6 6]</syntaxhighlight> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<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</ |
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}} |
||
< |
<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.</ |
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}}== |
||
< |
<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</ |
console.log arr</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,719: | Line 1,719: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
< |
<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)))))</ |
(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}}== |
||
< |
<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; |
||
}</ |
}</syntaxhighlight> |
||
A lower level implementation: |
A lower level implementation: |
||
< |
<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; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Dart}}== |
=={{header|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}}== |
||
< |
<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</ |
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}} |
||
< |
<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: | ||
} |
} |
||
} |
} |
||
}</ |
}</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[]</ |
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. |
||
< |
<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}}== |
||
< |
<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</ |
(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#}}== |
||
< |
<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</ |
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. |
||
< |
<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 </ |
.array example 10 heapsort .array </syntaxhighlight> |
||
< |
<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 |
||
< |
<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</ |
end program Heapsort_Demo</syntaxhighlight> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<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</ |
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. |
||
< |
<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 )</ |
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.) |
||
< |
<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) |
||
}</ |
}</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: |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 2,700: | Line 2,700: | ||
root = child |
root = child |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Loose translation of the pseudocode: |
Loose translation of the pseudocode: |
||
< |
<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 |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<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]))</ |
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 |
||
< |
<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))</ |
heapsort = (map fst) . toList . build . map (\x->(x,x))</syntaxhighlight> |
||
e.g. |
e.g. |
||
< |
<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]]</ |
[[2,13],[5],[6,8,14,9],[6,9],[10,7]]</syntaxhighlight> |
||
=={{header|Haxe}}== |
=={{header|Haxe}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<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); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,830: | Line 2,830: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
< |
<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</ |
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''' |
||
< |
<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 |
||
)</ |
)</syntaxhighlight> |
||
'''Examples''' |
'''Examples''' |
||
< |
<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</ |
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. |
||
< |
<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]))</ |
(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. |
||
< |
<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; |
||
} |
} |
||
}</ |
}</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]) |
||
})</ |
})</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. |
||
< |
<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}}== |
||
< |
<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)) |
||
</ |
</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}}== |
||
< |
<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(", ")) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,275: | Line 3,275: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
< |
<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</ |
end sub</syntaxhighlight> |
||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
||
< |
<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}}== |
||
< |
<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')</ |
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;</ |
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}}== |
||
< |
<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]; |
||
] |
] |
||
]</ |
]</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. |
||
< |
<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</ |
end</syntaxhighlight> |
||
Sample Usage: |
Sample Usage: |
||
< |
<syntaxhighlight lang="matlab">>> heapSort([4 3 1 5 6 2]) |
||
ans = |
ans = |
||
1 2 3 4 5 6</ |
1 2 3 4 5 6</syntaxhighlight> |
||
=={{header|MAXScript}}== |
=={{header|MAXScript}}== |
||
< |
<syntaxhighlight lang="maxscript">fn heapify arr count = |
||
( |
( |
||
local s = count /2 |
local s = count /2 |
||
Line 3,686: | Line 3,686: | ||
) |
) |
||
)</ |
)</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: | ||
< |
<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:</ |
%%% end:</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,813: | Line 3,813: | ||
=={{header|NetRexx}}== |
=={{header|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</ |
return a</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,918: | Line 3,918: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<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</ |
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}} |
||
< |
<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: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<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;;</ |
done;;</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<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 ();;</ |
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. |
||
< |
<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}}</ |
{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 :-) |
||
< |
<syntaxhighlight lang="pascal">program HeapSortDemo; |
||
type |
type |
||
Line 4,179: | Line 4,179: | ||
end; |
end; |
||
writeln; |
writeln; |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,189: | Line 4,189: | ||
=={{header|Perl}}== |
=={{header|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}}== |
||
<!--< |
<!--<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> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,281: | Line 4,281: | ||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
< |
<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.</ |
L[J] := T.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,332: | Line 4,332: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
< |
<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) ) ) )</ |
(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}}== |
||
< |
<syntaxhighlight lang="pli">*process source xref attributes or(!); |
||
/********************************************************************* |
/********************************************************************* |
||
* Pseudocode found here: |
* Pseudocode found here: |
||
Line 4,431: | Line 4,431: | ||
End; |
End; |
||
End;</ |
End;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,489: | Line 4,489: | ||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
< |
<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</ |
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}}== |
||
< |
<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</ |
EndProcedure</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<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</ |
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]]. |
||
< |
<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 </ |
say " --> " hsort echo </syntaxhighlight> |
||
''' Output:''' |
''' Output:''' |
||
Line 4,696: | Line 4,696: | ||
=={{header|Racket}}== |
=={{header|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 |
<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;</ |
say 'Output = ' ~ @data;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 4,764: | Line 4,764: | ||
Indexing of the array starts with '''1''' (one), but can be programmed to start with zero. |
Indexing of the array starts with '''1''' (one), but can be programmed to start with zero. |
||
< |
<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</ |
show: do s=1 for #; say ' element' right(s, length(#)) arg(1) @.s; end; return</syntaxhighlight> |
||
{{out|output|text= when using the default (epichoric Greek alphabet) for input:}} |
{{out|output|text= when using the default (epichoric Greek alphabet) for input:}} |
||
(Shown at three-quarter size.) |
(Shown at three-quarter size.) |
||
Line 4,910: | Line 4,910: | ||
===version 2=== |
===version 2=== |
||
< |
<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</ |
Return</syntaxhighlight> |
||
Output: see PL/I |
Output: see PL/I |
||
=={{header|Ring}}== |
=={{header|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}}== |
||
< |
<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</ |
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. |
||
< |
<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: | ||
} |
} |
||
} |
} |
||
}</ |
}</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. |
||
< |
<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); |
||
}</ |
}</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. |
||
< |
<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) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
{{works with|Scheme|R<math>^5</math>RS}} |
{{works with|Scheme|R<math>^5</math>RS}} |
||
< |
<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</ |
uriah</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>done |
<pre>done |
||
Line 5,250: | Line 5,250: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<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;</ |
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}}== |
||
< |
<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</ |
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. |
||
< |
<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. |
||
< |
<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) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<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) |
||
} |
} |
||
}</ |
}</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}} |
||
< |
<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 |
||
}</ |
}</syntaxhighlight> |
||
Demo code: |
Demo code: |
||
< |
<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}} |
||
< |
<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</ |
RETURN</syntaxhighlight> |
||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
{{trans|C++}} |
{{trans|C++}} |
||
< |
<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); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,869: | Line 5,869: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
< |
<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</ |
End Sub</syntaxhighlight> |
||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
< |
<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() |
||
}</ |
}</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}} |
||
< |
<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() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,990: | Line 5,990: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<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; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">heapSort(L(170, 45, 75, -90, -802, 24, 2, 66)).println(); |
||
heapSort("this is a test".split("")).println();</ |
heapSort("this is a test".split("")).println();</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |