Anonymous user
Sorting algorithms/Heapsort: Difference between revisions
m
{{out}}
m ({{out}}) |
|||
Line 1:
{{task|Sorting Algorithms}} {{Sorting Algorithm}} {{wikipedia|Heapsort}}
{{omit from|GUISS}}▼
[[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.
Heapsort requires random access, so can only be used on an array-like data structure.
Pseudocode:
Line 230 ⟶ 235:
ENDWHILE
ENDPROC</lang>
{{out}}
<pre>
-31 0 1 2 2 4 65 83 99 782
Line 358 ⟶ 363:
std::cout << "\n";
}</lang>
{{out}}
<pre>
-199 -52 2 3 33 56 99 100 177 200
Line 1,129 ⟶ 1,134:
* Beware missing trailing 'returns' when translating pseudo-code. For amusement try comment out the return at the end of 'shiftdown'
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.
{{out|Abbreviated sample output}}
<pre>Sorting Demo using procedure heapsort
Line 1,616 ⟶ 1,622:
heapSort a
echo a</lang>
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
Line 2,044 ⟶ 2,050:
End;</lang>
{{out}}
<pre>
element 0 before sort ---letters of the modern Greek Alphabet---
Line 2,246 ⟶ 2,252:
say copies('─', 79) /*show a separator line. */
return</lang>
<pre style="height:30ex;overflow:scroll">
element 1 before sort: ---modern Greek alphabet letters---
Line 2,773 ⟶ 2,779:
L(" "," "," ","a","e","h","i","i","s","s","s","t","t","t")
</pre>
▲{{omit from|GUISS}}
| |||