Sorting algorithms/Heapsort: Difference between revisions

=={{header|Groovy}}==

Loose translation of the pseudocode:

<lang groovy>def makeSwap = { a, i, j -> print "."; def t = a[j]; a[j] = a[i]; a[i] = t }

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

def siftDown = { a, start, end ->

def p = start

while (p*2 < end) {

def c = p*2 + ((p*2 + 1 < end && a[p*2 + 2] > a[p*2 + 1]) ? 2 : 1)

if (checkSwap(a, c, p)) { p = c }

else { return }

}

}

def heapify = {

(((it.size()-2).intdiv(2))..0).each { start -> siftDown(it, start, it.size()-1) }

}

def heapSort = { list ->

heapify(list)

(0..<(list.size())).reverse().each { end ->

makeSwap(list, 0, end)

siftDown(list, 0, end-1)

}

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>

Output:

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