Content deleted Content added
Citation bot (talk | contribs) m Alter: url. Add: volume. Removed URL that duplicated unique identifier. | You can use this bot yourself. Report bugs here.| Activated by User:Nemo bis | via #UCB_webform |
Citation bot (talk | contribs) Add: s2cid, author pars. 1-1. Removed URL that duplicated unique identifier. Removed parameters. Some additions/deletions were actually parameter name changes. | You can use this bot yourself. Report bugs here. | Activated by AManWithNoPlan | All pages linked from User:AManWithNoPlan/sandbox2 | via #UCB_webform_linked |
||
Line 1:
In computer science, '''adaptive heap sort''' is a [[Comparison sort|comparison-based]] [[sorting algorithm]] of the [[Adaptive sort|adaptive sort family]]. It is a variant of [[Heapsort|heap sort]] that performs better when the data contains existing order. Published by [[Christos Levcopoulos]] and [[Ola Petersson]] in 1992, the algorithm utilizes a new measure of presortedness, ''Osc,'' as the number of oscillations.<ref name=":0">{{Cite journal|
== Heapsort ==
Heap sort is a sorting algorithm that utilizes [[binary heap]] data structure. The method treats an array as a complete [[binary tree]] and builds up a Max-Heap/Min-Heap to achieve sorting.<ref name=":1">{{Cite journal|
# Build a Max-Heap(Min-Heap): put all the data into the heap so that all nodes are either greater than or equal (less than or equal to for ''Min-Heap'') to each of its child nodes.
Line 74:
=== Other measures ===
Besides the original Osc measurement, other known measures include the number of inversions ''Inv'', the number of runs ''Runs'', the number of blocks ''Block'', and the measures ''Max'', ''Exc'' and ''Rem''. Most of these different measurements are related for adaptive heap sort. Some measures dominate the others: every Osc-optimal algorithm is Inv optimal and Runs optimal; every Inv-optimal algorithm is Max optimal; and every Block-optimal algorithm is Exc optimal and Rem optimal.<ref name=":2">{{Cite journal|
== Algorithm ==
| |||