Anonymous user
Sorting algorithms/Heapsort: Difference between revisions
added python translated from ruby
m (→{{header|Ruby}}: output fmt) |
(added python translated from ruby) |
||
Line 46:
'''return'''
Write a function to sort a collection of integers using heapsort.
=={{header|Python}}==
<lang python>def heapsort(lst):
''' Heapsort. Note: this function sorts in-place (it mutates the list). '''
# in pseudo-code, heapify only called once, so inline it here
for start in range((len(lst)-2)/2, -1, -1):
siftdown(lst, start, len(lst)-1)
for end in range(len(lst)-1, 0, -1):
lst[end], lst[0] = lst[0], lst[end]
siftdown(lst, 0, end - 1)
return lst
def siftdown(lst, start, end):
root = start
while True:
child = root * 2 + 1
if child > end: break
if child + 1 <= end and lst[child] < lst[child + 1]:
child += 1
if lst[root] < lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break</lang>
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|Ruby}}==
| |||