Sorting algorithms/Heapsort: Difference between revisions

{{trans|Python}}

 

V root = start

L

V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

heapsort(&arr)

 

{{out}}

{{trans|PL/I}}

The program uses ASM structured macros and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.

HEAPS CSECT

USING HEAPS,R13 base register

N DC A((N-A)/L'A) number of items

YREGS

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program heapSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

=={{header|ActionScript}}==

for (var start:int = (data.length-2)/2; start >= 0; start--) {

siftDown(data, start, data.length);

}

}

 

=={{header|Ada}}==

This implementation is a generic heapsort for unconstrained arrays.

type Element_Type is private;

type Index_Type is (<>);

type Collection is array(Index_Type range <>) of Element_Type;

with function "<" (Left, right : element_type) return boolean is <>;

procedure Swap(Left : in out Element_Type; Right : in out Element_Type) is

Temp : Element_Type := Left;

end loop;

Demo code:

with Ada.Text_Io; use Ada.Text_Io;

 

end loop;

New_Line;

 

=={{header|ALGOL 68}}==

PROC swap = (REF []INT array, INT first, INT second) VOID:

(

print(("After: ", a))

 

{{out}}

<pre>

=={{header|AppleScript}}==

===Binary heap===

-- Heap sort algorithm: J.W.J. Williams.

on heapSort(theList, l, r) -- Sort items l thru r of theList.

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.

 

{{output}}

 

===Ternary heap===

-- Heap sort algorithm: J.W.J. Williams.

on heapSort(theList, l, r) -- Sort items l thru r of theList.

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.

 

{{output}}

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

 

/* ARM assembly Raspberry PI */

iMagicNumber: .int 0xCCCCCCCD

 

 

=={{header|Arturo}}==

 

root: start

a: new items

]

 

 

{{out}}

 

=={{header|AutoHotkey}}==

Local end

end := %a%0

heapSort("a")

ListVars

 

=={{header|BBC BASIC}}==

test() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCheapsort(test())

IF a(r%) < a(c%) SWAP a(r%), a(c%) : r% = c% ELSE ENDPROC

ENDWHILE

{{out}}

<pre>

 

=={{header|BCPL}}==

 

GET "libhdr.h"

}

newline()

 

=={{header|C}}==

 

int max (int *a, int n, int i, int j, int k) {

return 0;

}

 

=={{header|C sharp|C#}}==

using System.Collections.Generic;

using System.Text;

HeapSort(s, 0, s.Length, StringComparer.CurrentCultureIgnoreCase);

}

 

=={{header|C++}}==

Uses C++11. Compile with

g++ -std=c++11 heap.cpp

#include <iterator>

#include <iostream>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

{{out}}

<pre>

Uses C++11. Compile with

g++ -std=c++11

#include <iostream>

#include <vector>

heap_sort(data);

for(int i : data) cout << i << " ";

{{out}}

<pre>

 

=={{header|Clojure}}==

(assoc a i (nth a j) j (nth a i)))

([a]

(heap-sort a <)))

Example usage:

[1 2 2 3 4 6 6]

user> (heapsort [1 2 4 6 2 3 6] >)

[6 6 4 3 2 2 1]

user> (heapsort (list 1 2 4 6 2 3 6))

 

=={{header|CLU}}==

% may be any type that can be compared.

heapsort = cluster [T: type] is sort

stream$puts(po, "After sorting: ")

print_arr[int](po,arr,5)

{{out}}

<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17

=={{header|COBOL}}==

{{works with|GnuCOBOL}}

*> This code is dedicated to the public domain

*> This is GNUCOBOL 2.0

end-perform

.

{{out}}

<pre>prompt$ cobc -xj heapsort.cob

 

=={{header|CoffeeScript}}==

heap_sort = (arr) ->

put_array_in_heap_order(arr)

arr = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]

heap_sort arr

{{out}}

<pre>

 

=={{header|Common Lisp}}==

(make-array length :adjustable t :fill-pointer 0))

 

(let ((h (make-heap (length sequence))))

(map nil #'(lambda (e) (heap-insert h e predicate)) sequence)

Example usage:

<pre>(heapsort (vector 1 9 2 8 3 7 4 6 5) '<) ; #(1 2 3 4 5 6 7 8 9)

 

=={{header|D}}==

 

void heapSort(T)(T[] data) /*pure nothrow @safe @nogc*/ {

items.heapSort;

items.writeln;

 

A lower level implementation:

 

void heapSort(R)(R seq) pure nothrow @safe @nogc {

data.heapSort;

data.writeln;

 

=={{header|Dart}}==

void heapSort(List a) {

int count = a.length;

}

 

=={{header|Delphi}}==

See [https://rosettacode.org/wiki/Sorting_algorithms/Heapsort#Pascal Pascal].

 

=={{header|Draco}}==

word root, child;

int temp;

write("After sorting: ");

for i from 0 upto 9 do write(a[i]:5) od

{{out}}

<pre>Before sorting: 9 -5 3 3 24 -16 3 -120 250 17

=={{header|E}}==

{{trans|Python}}

def cswap(c, a, b) {

def t := c[a]

}

}

 

=={{header|EasyLang}}==

 

for i = 1 to n - 1

if data[i] > data[(i - 1) / 2]

data[] = [ 29 4 72 44 55 26 27 77 92 5 ]

call sort

 

=={{header|EchoLisp}}==

We use the heap library and the '''heap-pop''' primitive to implement heap-sort.

(lib 'heap)

 

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

 

 

=={{header|Eiffel}}==

class

HEAPSORT

 

end

Test:

class

APPLICATION

 

end

{{out}}

<pre>

 

=={{header|Elixir}}==

def heapSort(list) do

len = length(list)

end

 

 

{{out}}

 

=={{header|F Sharp|F#}}==

let temp = a.[i]

a.[i] <- a.[j]

for term = n - 1 downto 1 do

swap a term 0

 

=={{header|Forth}}==

This program assumes that return addresses simply reside as a single cell on the Return Stack. Most Forth compilers fulfill this requirement.

70 , 61 , 63 , 37 , 63 , 25 , 46 , 92 , 38 , 87 ,

 

: .array 10 0 do example i cells + ? loop cr ;

 

 

 

\ Written in ANS-Forth; tested under VFX.

\ Requires the novice package: http://www.forth.org/novice.html

 

10 test-sort

{{out}}

<pre style="height:8ex;overflow:scroll">

{{works with|Fortran|90 and later}}

Translation of the pseudocode

implicit none

end subroutine siftdown

 

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

' for boundary checks on array's compile with: fbc -s console -exx

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>Unsorted

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.

 

heapify( a )

end = a.length() - 1

a = array( [7, 2, 6, 1, 9, 5, 0, 3, 8, 4] )

heapSort( a )

 

{{out}}

 

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.)

 

import (

heapSort(sort.IntSlice(a))

fmt.Println("after: ", a)

{{out}}

<pre>

</pre>

If you want to implement it manually:

 

import (

root = child

}

 

=={{header|Groovy}}==

Loose translation of the pseudocode:

 

def checkSwap = { list, i, j = i+1 -> [(list[i] > list[j])].find{ it }.each { makeSwap(list, i, j) } }

}

list

Test:

{{out}}

<pre>.......................................................................[4, 12, 14, 23, 24, 24, 31, 35, 38, 46, 51, 57, 57, 58, 76, 78, 89, 92, 95, 97, 99]

=={{header|Haskell}}==

Using package [http://hackage.haskell.org/package/fgl fgl] from HackageDB

Heap(..),insert,findMin,deleteMin)

 

 

heapsort :: Ord a => [a] -> [a]

e.g.

 

=={{header|Haxe}}==

{{trans|D}}

@:generic

private static function siftDown<T>(arr: Array<T>, start:Int, end:Int) {

Sys.println('Sorted Strings: ' + stringArray);

}

{{out}}

<pre>

 

=={{header|Icon}} and {{header|Unicon}}==

demosort(heapsort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")

end

}

return X

Algorithm notes:

* This is a fairly straight forward implementation of the pseudo-code with 'heapify' coded in-line.

{{eff note|J|/:~}}

'''Translation of the pseudocode'''

 

siftDown=: 4 : 0

z=. siftDown&.>/ (c,~each i.<.c%2),<y NB. heapify

> ([ siftDown swap~)&.>/ (0,each}.i.c),z

'''Examples'''

1 1 2 3 4 5 6 7 8 9

 

heapSort &. (a.&i.) 'aqwcdhkij'

 

=={{header|Janet}}==

Although Janet is a (functional) Lisp, it has support for [https://janet-lang.org/docs/data_structures/arrays.html mutable arrays] and imperative programming.

 

(defn swap [l a b]

(let [aval (get l a) bval (get l b)]

 

# NOTE: Makes a copy of input array. Output is mutable

{{out}}

<pre>

=={{header|Java}}==

Direct translation of the pseudocode.

int count = a.length;

 

return;

}

 

=={{header|Javascript}}==

function heapSort(arr) {

heapify(arr)

heapSort(arr)

expect(arr).toStrictEqual([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])

{{out}}

<pre>

 

Since jq is a purely functional language, the putative benefits of the heapsort algorithm do not accrue here.

$a

| .[$i] as $t

"Before: \(.)",

"After : \(heapSort)\n"

{{out}}

<pre>

 

=={{header|Julia}}==

a[i], a[j] = a[j], a[i]

end

println("Unsorted: $a")

println("Heap sorted: ", heapsort!(a))

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]

 

=={{header|Kotlin}}==

 

fun heapSort(a: IntArray) {

println(a.joinToString(", "))

}

 

{{out}}

 

=={{header|Liberty BASIC}}==

 

data 6, 5, 3, 1, 8, 7, 2, 4

next i

print

 

=={{header|Lobster}}==

// (end represents the limit of how far down the heap to sift)

var root = start

heapSort(inputs)

print ("sorted: " + inputs)

{{out}}

<pre>

=={{header|LotusScript}}==

 

Public Sub heapsort(pavIn As Variant)

Dim liCount As Integer, liEnd As Integer

wend

End Sub

 

=={{header|M4}}==

 

define(`randSeed',141592653)

show(`a')

heapsort(`a')

 

=={{header|Maple}}==

local temp:

temp := arr[a]:

arr := Array([17,3,72,0,36,2,3,8,40,0]);

heapsort(arr);

{{Out|Output}}

<pre>[0,0,2,3,3,8,17,36,40,72]</pre>

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

While[(root*2) <= theEnd,

child = root*2;

count--; list = siftDown[list,1,count];

]

{{out}}

<pre>heapSort@{2,3,1,5,7,6}

=={{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.

 

function list = siftDown(list,root,theEnd)

end

Sample Usage:

 

ans =

 

 

=={{header|MAXScript}}==

(

local s = count /2

)

Output:

a = for i in 1 to 10 collect random 0 9

#(7, 2, 5, 6, 1, 5, 4, 0, 1, 6)

heapSort a

#(0, 1, 1, 2, 4, 5, 5, 6, 6, 7)

 

=={{header|Mercury}}==

 

 

 

:- module heapsort_task.

%%% mode: mercury

%%% prolog-indent-width: 2

 

{{out}}

 

=={{header|NetRexx}}==

options replace format comments java crossref savelog symbols binary

 

end root

 

{{out}}

<pre>

 

=={{header|Nim}}==

var root = start

while root * 2 + 1 < ending:

var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]

heapSort a

{{out}}

<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>

=={{header|Objeck}}==

{{trans|Java}}

class HeapSort {

function : Main(args : String[]) ~ Nil {

}

}

 

=={{header|OCaml}}==

 

let swap i j =

swap term 0;

sift 0 term;

Usage:

heapsort a;

Array.iter (Printf.printf "%d ") a;;

heapsort b;

Array.iter print_char b;;

{{out}}

<pre>

=={{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.

proc {HeapSort A}

Low = {Array.low A}

in

{HeapSort Arr}

 

=={{header|Pascal}}==

An example, which works on arrays with arbitrary bounds :-)

 

type

end;

writeln;

{{out}}

<pre>

 

=={{header|Perl}}==

 

my @a = (4, 65, 2, -31, 0, 99, 2, 83, 782, 1);

return $m;

}

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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>

{{out}}

<pre>

 

=={{header|Picat}}==

_ = random2(),

A = [random(-10,10) : _ in 1..30],

T = L[I],

L[I] := L[J],

 

{{out}}

 

=={{header|PicoLisp}}==

(let Cnt (length A)

(for (Start (/ Cnt 2) (gt0 Start) (dec Start))

(NIL (> (get A Child) (get A Root)))

(xchg (nth A Root) (nth A Child))

{{out}}

<pre>: (heapSort (make (do 9 (link (rand 1 999)))))

 

=={{header|PL/I}}==

/*********************************************************************

* Pseudocode found here:

End;

 

{{out}}

<pre>

 

=={{header|PL/M}}==

 

/* HEAP SORT AN ARRAY OF 16-BIT INTEGERS */

 

CALL BDOS(0,0);

{{out}}

<pre>0 1 2 2 3 4 8 31 65 99 782</pre>

 

=={{header|PowerShell}}==

function heapsort($a, $count) {

$a = heapify $a $count

$array = @(60, 21, 19, 36, 63, 8, 100, 80, 3, 87, 11)

"$(heapsort $array $array.Count)"

<b>Output:</b>

<pre>

 

=={{header|PureBasic}}==

Declare siftDown(Array a(1), start, ending)

 

EndIf

Wend

 

=={{header|Python}}==

''' Heapsort. Note: this function sorts in-place (it mutates the list). '''

 

root = child

else:

Testing:

<pre>>>> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

This uses code from [[Priority queue#Quackery]].

 

dup pqsize times

[ frompq rot join swap ]

[] 23 times [ 90 random 10 + join ]

say " " dup echo cr

 

''' Output:'''

 

=={{header|Racket}}==

#lang racket

(require (only-in srfi/43 vector-swap!))

(sift-down! 0 (- end 1)))

xs)

 

=={{header|Raku}}==

(formerly Perl 6)

for ( 0 ..^ +@list div 2 ).reverse -> $start {

_sift_down $start, @list.end, @list;

say 'Input = ' ~ @data;

@data.&heap_sort;

{{out}}

<pre>

 

Indexing of the array starts with &nbsp; '''1''' &nbsp; (one), &nbsp; but can be programmed to start with zero.

parse arg x; call init /*use args or default, define @ array.*/

call show "before sort:" /*#: the number of elements in array*/

end /*while*/; @.i= $; return /*define lowest.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default &nbsp; (epichoric Greek alphabet) &nbsp; for input:}}

(Shown at three-quarter size.)

 

===version 2===

* Translated from PL/I

* 27.07.2013 Walter Pachl

Say 'element' format(j,2) txt a.j

End

Output: see PL/I

 

=={{header|Ring}}==

# Project : Sorting algorithms/Heapsort

 

svect = left(svect, len(svect) - 1)

see svect + nl

Output:

<pre>

 

=={{header|Ruby}}==

def heapsort

self.dup.heapsort!

end

end

Testing:

<pre>irb(main):035:0> ary = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]

{{trans|Python}}

This program allows the caller to specify an arbitrary function by which an order is determined.

let mut v = [4, 6, 8, 1, 0, 3, 2, 2, 9, 5];

heap_sort(&mut v, |x, y| x < y);

}

}

 

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

 

 

fn main() {

let sorted = BinaryHeap::from(src).into_sorted_vec();

println!("{:?}", sorted);

 

=={{header|Scala}}==

{{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.

import scala.annotation.tailrec // Ensure functions are tail-recursive

import ord._

siftDown(0, i)

}

 

=={{header|Scheme}}==

{{works with|Scheme|R<math>^5</math>RS}}

(define (swap! v i j)

(define temp (vector-ref v i))

(define uriah (list->vector '(3 5 7 9 0 8 1 4 2 6)))

(heapsort uriah)

{{out}}

<pre>done

 

=={{header|Seed7}}==

local

var elemType: help is elemType.value;

downheap(arr, 1, n);

until n <= 1;

Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#heapSort]

 

=={{header|SequenceL}}==

import <Utilities/Sequence.sl>;

 

in

setElementAt(setElementAt(list, i, vals.B), j, vals.A);

 

=={{header|Sidef}}==

var root = start;

while ((2*root + 1) <= end) {

say arr; # prints the unsorted array

heap_sort(arr, arr.len); # sorts the array in-place

{{out}}

<pre>[10, 5, 2, 1, 7, 6, 4, 8, 3, 9]

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.

 

functor PairingHeap(type t

val cmp : t * t -> order) =

val test_3 = heapsort [6,2,7,5,8,1,3,4] = [1, 2, 3, 4, 5, 6, 7, 8]

end;

 

=={{header|Stata}}==

Variant with siftup and siftdown, using Mata.

 

k = i

while (k > 1) {

siftdown(a, i-1)

}

 

=={{header|Swift}}==

var count = list.count

shiftDown(&list, 0, end)

}

 

=={{header|Tcl}}==

Based on the algorithm from Wikipedia:

{{works with|Tcl|8.5}}

 

proc heapsort {list {count ""}} {

lset a $x [lindex $a $y]

lset a $y $tmp

Demo code:

{{out}}

<pre>0 1 2 3 4 5 6 7 8 9</pre>

=={{header|True BASIC}}==

{{trans|Liberty BASIC}}

!creamos la matriz y la inicializamos

LET lim = 20

CALL printArray (lim)

END

 

 

=={{header|uBasic/4tH}}==

n = FUNC (_InitArray)

PROC _ShowArray (n)

 

PRINT

 

=={{header|Vala}}==

{{trans|C++}}

if (array[i1] == array[i2])

return;

stdout.printf("%d ", i);

}

 

{{out}}

=={{header|VBA}}==

{{trans|FreeBASIC}}

Dim root As Long : root = start

Dim lb As Long : lb = LBound(list)

SiftDown list(), 0, eend

Wend

 

=={{header|Wren}}==

var root = start

while (root*2 + 1 <= end) {

System.print("After : %(a)")

System.print()

 

{{out}}

Alternatively, we can just call a library method.

{{libheader|Wren-sort}}

 

var as = [ [4, 65, 2, -31, 0, 99, 2, 83, 782, 1], [7, 5, 2, 6, 1, 4, 2, 6, 3] ]

System.print("After : %(a)")

System.print()

 

{{out}}

 

=={{header|zkl}}==

n := a.len();

foreach start in ([(n-2)/2 .. 0,-1])

start = child;

}

{{out}}

<pre>