Content deleted Content added
mNo edit summary |
mNo edit summary |
||
Line 125:
Let's expand a little bit on the next two segments that the main algorithm recurs on. Because we are using strict comparators (>, <) in the '''{{Mono|"do...while"}}''' loops to prevent ourselves from running out of range, there's a chance that the pivot itself gets swapped with other elements in the partition function. Therefore, '''the index returned in the partition function isn't necessarily where the actual pivot is.''' Consider the example of '''{{Mono|[5, 2, 3, 1, 0]}}''', following the scheme, after the first partition the array becomes '''{{Mono|[0, 2, 1, 3, 5]}}''', the "index" returned is 2, which is the number 1, when the real pivot, the one we chose to start the partition with was the number 3. With this example, we see how it is necessary to include the returned index of the partition function in our subsequent recursions. As a result, we are presented with the choices of either recursing on {{mono|(lo..p)}} and {{mono|(p+1..hi)}}, or {{mono|(lo..p-1)}} and {{mono|(p..hi)}}. Which of the two options we choose depends on which index ('''i''' or '''j''') we return in the partition function when the indices cross, and how we choose our pivot in the partition function ('''floor''' v.s. '''ceiling''').
The choice of recursing on {{mono|(lo..p-1)}} and {{mono|(p..hi)}} follows the exact same logic as above. '''Because the right half of the recursion includes the returned index, it is the partition function's job to exclude the "head" in non-advancing scenarios.''' The index i (the "latter" index after the indices cross) in the partition function needs to be returned, and "ceiling" needs to be chosen as the pivot. The two nuances are clear, again, when considering the examples of sorting an array where multiple identical elements exist ('''{{Mono|[0, 0]}}'''), and an already sorted array '''{{Mono|[0, 1]}}''' respectively. It is noteworthy that with version of recursion, for the same reason, choice of the first element as pivot must be avoided.
Line 377:
=== Generalization ===
[[Richard J. Cole|Richard Cole]] and David C. Kandathil, in 2004, discovered a one-parameter family of sorting algorithms, called partition sorts, which on average (with all input orderings equally likely) perform at most <math>n\log n + {O}(n)</math> comparisons (close to the information theoretic lower bound) and <math>{\Theta}(n\log n)</math> operations; at worst they perform <math>{\Theta}(n\log^2 n)</math> comparisons (and also operations); these are in-place, requiring only additional <math>{O}(\log n)</math> space. Practical efficiency and smaller variance in performance were demonstrated against
== See also ==
| |||