65 lines
3.0 KiB
Plaintext
65 lines
3.0 KiB
Plaintext
{{Sorting Algorithm}}
|
||
[[Category:Sorting]]
|
||
{{wikipedia|Heapsort}}
|
||
{{omit from|GUISS}}
|
||
|
||
<br>
|
||
[[wp:Heapsort|Heapsort]] is an in-place sorting algorithm with worst case and average complexity of <span style="font-family: serif">O(''n'' log''n'')</span>.
|
||
|
||
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.
|
||
|
||
A heap sort requires random access, so can only be used on an array-like data structure.
|
||
|
||
Pseudocode:
|
||
'''function''' heapSort(a, count) '''is'''
|
||
'''input:''' an unordered array ''a'' of length ''count''
|
||
|
||
<span style="color: grey">''(first place a in max-heap order)''</span>
|
||
heapify(a, count)
|
||
|
||
end := count - 1
|
||
'''while''' end > 0 '''do'''
|
||
<span style="color: grey">''(swap the root(maximum value) of the heap with the''
|
||
''last element of the heap)''</span>
|
||
swap(a[end], a[0])
|
||
<span style="color: grey">''(decrement the size of the heap so that the previous''
|
||
''max value will stay in its proper place)''</span>
|
||
end := end - 1
|
||
<span style="color: grey">''(put the heap back in max-heap order)''</span>
|
||
siftDown(a, 0, end)
|
||
|
||
|
||
'''function''' heapify(a,count) '''is'''
|
||
<span style="color: grey">''(start is assigned the index in ''a'' of the last parent node)''</span>
|
||
start := (count - 2) / 2
|
||
|
||
'''while''' start ≥ 0 '''do'''
|
||
<span style="color: grey">''(sift down the node at index start to the proper place''
|
||
''such that all nodes below the start index are in heap''
|
||
''order)''</span>
|
||
siftDown(a, start, count-1)
|
||
start := start - 1
|
||
<span style="color: grey">''(after sifting down the root all nodes/elements are in heap order)''</span>
|
||
|
||
'''function''' siftDown(a, start, end) '''is'''
|
||
<span style="color: grey">''(''end'' represents the limit of how far down the heap to sift)''</span>
|
||
root := start
|
||
|
||
'''while''' root * 2 + 1 ≤ end '''do''' <span style="color: grey">''(While the root has at least one child)''</span>
|
||
child := root * 2 + 1 <span style="color: grey">''(root*2+1 points to the left child)''</span>
|
||
<span style="color: grey">''(If the child has a sibling and the child's value is less than its sibling's...)''</span>
|
||
'''if''' child + 1 ≤ end '''and''' a[child] < a[child + 1] '''then'''
|
||
child := child + 1 <span style="color: grey">''(... then point to the right child instead)''</span>
|
||
'''if''' a[root] < a[child] '''then''' <span style="color: grey">''(out of max-heap order)''</span>
|
||
swap(a[root], a[child])
|
||
root := child <span style="color: grey">''(repeat to continue sifting down the child now)''</span>
|
||
'''else'''
|
||
'''return'''
|
||
|
||
<br>
|
||
Write a function to sort a collection of integers using heapsort.
|
||
<br><br>
|
||
|