Adaptive heap sort: Difference between revisions

Revision as of 01:51, 17 November 2019

Revision as of 15:38, 1 December 2019

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|last=Levcopoulos|first=C.|last2=Petersson|first2=O.|date=1993-05-01|title=Adaptive Heapsort|url=http://www.sciencedirect.com/science/article/pii/S0196677483710217|journal=Journal of Algorithms|volume=14|issue=3|pages=395–413|doi=10.1006/jagm.1993.1021|issn=0196-6774}}</ref> Instead of putting all the data into the heap as the traditional heap sort did, adaptive heap sort only take part of the data into the heap so that the run time will reduce significantly when the presortedness of the data is high.<ref name=":0" />

== 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|last=Schaffer|first=R.|last2=Sedgewick|first2=R.|date=1993-07-01|title=The Analysis of Heapsort|url=http://www.sciencedirect.com/science/article/pii/S019667748371031X|journal=Journal of Algorithms|volume=15|issue=1|pages=76–100|doi=10.1006/jagm.1993.1031|issn=0196-6774}}</ref> It usually involves the following four steps.

# 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 68:

== Measures of presortedness ==

Measures of presortedness measures the existing order in a given sequence.<ref>{{Cite journal|last=Mannila|first=Heikki|date=April 1985|title=Measures of Presortedness and Optimal Sorting Algorithms|url=http://ieeexplore.ieee.org/document/5009382/|journal=IEEE Transactions on Computers|volume=C-34|issue=4|pages=318–325|doi=10.1109/TC.1985.5009382|issn=0018-9340}}</ref> These measures of presortedness decides the number of data that will be put in to the heap during the sorting process as well as the lower bound of running time.<ref name=":2" />

=== Oscillations (''Osc'') ===

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|last=Edelkamp|first=Stefan|last2=Elmasry|first2=Amr|last3=Katajainen|first3=Jyrki|date=2011|editor-last=Iliopoulos|editor-first=Costas S.|editor2-last=Smyth|editor2-first=William F.|title=Two Constant-Factor-Optimal Realizations of Adaptive Heapsort|url=https://link.springer.com/chapter/10.1007%2F978-3-642-25011-8_16|journal=Combinatorial Algorithms|volume=7056|series=Lecture Notes in Computer Science|publisher=Springer Berlin Heidelberg|pages=195–208|doi=10.1007/978-3-642-25011-8_16|isbn=9783642250118|url=https://semanticscholar.org/paper/5f9c8a1905e4b3d0dac0cdeaaac71843d49b17e7}}</ref>

== Algorithm ==