Content deleted Content added
Refix Algorithm |
AmirOnWiki (talk | contribs) |
||
Line 294:
From a bit complexity viewpoint, variables such as ''lo'' and ''hi'' do not use constant space; it takes {{math|''O''(log ''n'')}} bits to index into a list of {{mvar|n}} items. Because there are such variables in every stack frame, quicksort using Sedgewick's trick requires {{math|''O''((log ''n'')<sup>2</sup>)}} bits of space. This space requirement isn't too terrible, though, since if the list contained distinct elements, it would need at least {{math|''O''(''n'' log ''n'')}} bits of space.
Stack-free versions of Quicksort have been proposed. These use <math>O(1)</math> additional space (more precisely, one cell of the type
Another, less common, not-in-place, version of quicksort uses {{math|''O''(''n'')}} space for working storage and can implement a stable sort. The working storage allows the input array to be easily partitioned in a stable manner and then copied back to the input array for successive recursive calls. Sedgewick's optimization is still appropriate.▼
of the sorted records, in order to exchange records, and a constant number of integer variables used as indices).<ref>{{cite conference |last= Ďurian|first= Branislav|date= |title=Quicksort without a stack |url= |work= |book-title= Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium |conference=MFCS 1986 |___location= Bratislava, Czechoslovakia|publisher= Springer Berlin Heidelberg|access-date=}}</ref>
▲Another, less common, not-in-place, version of quicksort{{citation needed}} uses {{math|''O''(''n'')}} space for working storage and can implement a stable sort. The working storage allows the input array to be easily partitioned in a stable manner and then copied back to the input array for successive recursive calls. Sedgewick's optimization is still appropriate.
== Relation to other algorithms ==
| |||