Partial sorting: Difference between revisions

Revision as of 18:41, 7 April 2022

Revision as of 18:55, 7 April 2022

Line 24:

==Incremental sorting==

Incremental sorting is an "online"a version of the partial sorting problem, where the input is given up front but {{mvar|k}} is unknown: given a {{mvar|k}}-sorted array, it should be possible to extend the partially sorted part so that the array becomes {{math|(''k''+1)}}-sorted.{{r|paredes}}

[[Heap (data structure)|Heaps]] lead to an {{math|''O''(''n'' + ''k'' log ''n'')}} solution to onlineincremental partial sorting: first "heapify", in linear time, the complete input array to produce a min-heap. Then extract the minimum of the heap {{mvar|k}} times.<ref name="aofa04slides">{{cite conference |author=Conrado Martínez |year=2004 |title=On partial sorting |url=http://www.lsi.upc.edu/~conrado/research/talks/aofa04.pdf |conference=10th Seminar on the Analysis of Algorithms}}</ref>

A different incremental sort can be obtained by modifying quickselect. The version due to Paredes and Navarro maintains a [[stack (data structure)|stack]] of pivots across calls, so that incremental sorting can be accomplished by repeatedly requesting the smallest item of an array {{mvar|A}} from the following algorithm:<ref name="paredes">{{Cite conference| doi = 10.1137/1.9781611972863.16| chapter = Optimal Incremental Sorting| title = Proc. Eighth Workshop on Algorithm Engineering and Experiments (ALENEX)| pages = 171–182| year = 2006| last1 = Paredes | first1 = Rodrigo| last2 = Navarro | first2 = Gonzalo| isbn = 978-1-61197-286-3| citeseerx = 10.1.1.218.4119}}</ref>