Sorting algorithms/Heapsort: Difference between revisions

{{omit from|GUISS}}

The basic idea is to turn the array into a binary heap structure, which has the property that it allows efficient retrieval and removal of the maximal element.

We repeatedly "remove" the maximal element from the heap, thus building the sorted list from back to front.

 

Pseudocode:

'''else'''

'''return'''

Write a function to sort a collection of integers using heapsort.

 

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

After: +136 +326 +494 +633 +720 +760 +784 +813 +972 +980

</pre>

 

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

 

 

 

 

 

}

 

}

 

 

}

}

}

 

 

 

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

</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|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|E}}==

{{trans|Python}}

def cswap(c, a, b) {

def t := c[a]

}

}

=={{header|Eiffel}}==

class

HEAPSORT

sorted: is_sorted(ar)

end

 

is_sorted (ar: ARRAY [INTEGER]): BOOLEAN

--- Is 'ar' sorted in ascending order?

local

i: INTEGER

i := ar.lower

until

loop

if ar [i] > ar [i + 1] then

 

end

Test:

class

APPLICATION

 

end

{{out}}

<pre>

Unsorted: 5 91 13 99 7 35

Sorted: 5 7 13 35 91 99

</pre>

 

=={{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|FunL}}==

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)

 

where (x,r) = (findMin h,deleteMin h)

 

e.g.

 

=={{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|Java}}==

Direct translation of the pseudocode.

int count = a.length;

 

return;

}

 

=={{header|Javascript}}==

}

 

}

}

 

}

}

 

}

}

 

{{out}}

<pre>

</pre>

 

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

 

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

next i

print

 

 

=={{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')

 

While[(root*2) <= theEnd,

child = root*2;

]

]

heapSort[list_] := Module[{ count, start},

count = Length[list]; start = Floor[count/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|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 :-)

 

 

var

begin

end;

end;

end;

 

begin

{{out}}

<pre>

</pre>

 

=={{header|Perl}}==

 

 

}

}

}

 

}

}

 

{{out}}

<pre>

</pre>

 

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

element 24 after sort xi

element 25 after sort zeta

</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]

>>> heapsort(ary)

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

 

=={{header|Racket}}==

#lang racket

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

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

xs)

 

=={{header|REXX}}==

 

</pre>

 

* Translated from PL/I

* 27.07.2013 Walter Pachl

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

End

Output: see PL/I

 

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

irb(main):036:0> ary.heapsort

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