Sorting algorithms/Heapsort: Difference between revisions
Content added Content deleted
imported>SerErris (The code was completely unreadable for anyone want to find out what Heapsort does and how it works in groovy. This code should be much better to read. It is a adaption of the same code in JAVA example here.) |
imported>SerErris |
||
| Line 2,948: | Line 2,948: | ||
return a |
return a |
||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
This was the old code before if you are interested in how to code it in the most unreadable form: |
|||
<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 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 |
|||
} |
|||
</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])) |
<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])) |
||