Sorting algorithms/Heapsort: Difference between revisions

}

}</lang>

=={{header|Ada}}==

This implementation is a generic heapsort for unconstrained arrays.

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

procedure Generic_Heapsort(Item : in out Collection);</lang>

<lang Ada>procedure Generic_Heapsort(Item : in out Collection) is

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

New_Line;

end Test_Generic_Heapsort;</lang>

=={{header|AutoHotkey}}==

<lang AutoHotkey>heapSort(a) {

ListVars

MsgBox</lang>

=={{header|BCPL}}==

<lang BCPL>// This can be run using Cintcode BCPL freely available from www.cl.cam.ac.uk/users/mr10.

}

newline()

 

=={{header|C}}==

return 0;

}</lang>

If you want to be slightly more verbose

<lang cpp>#include <iostream>

 

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

<lang csharp>using System;

using System.Collections.Generic;

 

=={{header|Clojure}}==

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

</lang>

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

> coffee heap.coffee

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

 

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

<lang lisp>(defun make-heap (&optional (length 7))

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

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

(map-into sequence #'(lambda () (heap-delete-min h predicate)))))</lang>

Example usage:

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

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

 

=={{header|E}}==

{{trans|Python}}

<lang e>def heapsort := {

def cswap(c, a, b) {

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.

=={{header|Fortran}}==

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

Translation of the pseudocode

<lang fortran>program Heapsort_Demo

 

end program Heapsort_Demo</lang>

=={{header|Go}}==

Here's an ingenious solution that makes use of the heap module. Although the heap module usually implements an independent heap with push/pop operations, we use a helper type where the "pop" operation does not actually change the size of the underlying container, but changes a "heap length" variable indicating the length of the prefix of the underlying container that is considered "the heap".

 

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

 

fmt.Println("after: ", a)

}</lang>

<pre>

before: [170 45 75 -90 -802 24 2 66]

after: [-802 -90 2 24 45 66 75 170]

</pre>

If you want to implement it manually:

<lang go>package main

list

}</lang>

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

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>

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

..........................................................................................[0, 1, 4, 5, 7, 8, 12, 14, 18, 20, 31, 33, 44, 62, 70, 73, 75, 76, 78, 81, 82, 84, 88]</pre>

=={{header|Haskell}}==

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

<lang haskell>import Data.Graph.Inductive.Internal.Heap(

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

 

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

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

end

return X

end</lang>

Algorithm notes:

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

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]]. The full demosort exercises the named sort of a list with op = "numeric", "string", ">>" (lexically gt, descending),">" (numerically gt, descending), a custom comparator, and also a string.

on list : [ 3 14 1 5 9 2 6 3 ]

with op = &null: [ 1 2 3 3 5 6 9 14 ] (0 ms)

next i

print

 

=={{header|M4}}==

]

]</lang>

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

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

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

<lang MATLAB>function list = heapSort(list)

 

end</lang>

Sample Usage:

<lang MATLAB>>> heapSort([4 3 1 5 6 2])

end root

 

<pre>

UK London

=={{header|Objeck}}==

{{trans|Java}}

class HeapSort {

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

}

}

 

=={{header|OCaml}}==

Array.iter print_char b;;

print_newline ();;</lang>

<pre>

1 1 2 3 3 4 5 5 5 6 8 9 23 27 33 62 64 83 84 93 95 97

writeln;

end.</lang>

<pre>

The data before sorting:

say 'Input = ' ~ @data;

@data.&heap_sort;

Output = 1 2 3 4 5 6 7 8 9

</pre>

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

(setq Root Child) ) ) )</lang>

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

-> (1 167 183 282 524 556 638 891 902)</pre>

 

=={{header|REXX}}==

 

call gen@ /*generate array elements. */

 

say copies('─',80) /*show a seperator line. */

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

element 1 before sort: ---letters of the modern Greek Alphabet---

=={{header|Scala}}==

{{works with|Scala|2.8}}

<lang scala>def heapSort[T](a: Array[T])(implicit ord: Ordering[T]) {

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

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

(heapsort uriah)

 

=={{header|Seed7}}==

until n <= 1;

end func;</lang>

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

 

=={{header|Tcl}}==

{{works with|Tcl|8.5}}

<lang tcl>package require Tcl 8.5

Demo code:

<lang tcl>puts [heapsort {1 5 3 7 9 2 8 4 6 0}]</lang>

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