Quicksort: Difference between revisions

Revision as of 09:55, 4 December 2024

Revision as of 20:39, 6 December 2024

Line 123:

'''Subsequent recursions (expansion on previous paragraph)'''

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''').

Let's first examine the choice of recursing on {{mono|(lo..p)}} and {{mono|(p+1..hi)}}, with the example of sorting an array where multiple identical elements exist '''{{Mono|[0, 0]}}'''. If index i (the "latter" index) is returned after indices cross in the partition function, the index 1 would be returned after the first partition. The subsequent recursion on {{mono|(lo..p)}}would be on (0, 1), which corresponds to the exact same array '''{{Mono|[0, 0]}}'''. A non-advancing separation that causes infinite recursion is produced. It is therefore obvious that '''when recursing on {{mono|(lo..p)}} and {{mono|(p+1..hi)}}, because the left half of the recursion includes the returned index, it is the partition function's job to exclude the "tail" in non-advancing scenarios.''' Which is to say, index j (the "former" index when indices cross) should be returned instead of i. Going with a similar logic, when considering the example of an already sorted array '''{{Mono|[0, 1]}}''', the choice of pivot needs to be "floor" to ensure that the pointers stop on the "former" instead of the "latter" (with "ceiling" as the pivot, the index 1 would be returned and included in '''{{mono|(lo..p)}}''' causing infinite recursion). It is for the exact same reason why choice of the last element as pivot must be avoided.

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.

=== Implementation issues ===