Quicksort: rotation position after one section

Question

I read about quicksort, looking at various implementations, and I'm trying to wrap my head in something.

In this implementation (which, of course, works), the axis is selected as the middle element , and then the left and right pointers move to the right and left, replacing the elements with a turn around the bar.

I tried an array [4, 3, 2, 6, 8, 1, 0].

In the first section, the arch is 6, and all left elements are already less than 6, so the left pointer stops on the axis. On the right side, we will replace 0 with 6, and then with 1 and 8, so at the end of the first iteration, the array will look like this:

[4, 3, 2, 0, 1, 8, 6].

However, I got the impression that after each iteration in quick sort, the rod ends in its rightful place, so here it should end at position 5 of the array.

So, is it possible (and normal) that the rod does not end in the correct iteration or is it something obvious, am I missing?

Answer 1

There are many possible options for a quick sort algorithm. In this case, it is normal for the rod to not be in the right place in its iteration.

The defining feature of each variant of the quicksort algorithm is that after the section step we have a part at the beginning of the array, where all elements are less than or equal to the axis of rotation, and a non-overlapping part at the end of the array, where all elements are greater than or equal to the axis of rotation. Between them there can also be a part where each element is equal to the axis of rotation. This layout ensures that after sorting the left side and the right side with recursive calls, and leaving the middle part intact, the entire array will be sorted.

Note that in general, elements equal to pivot can go to any part of the array. A good quicksort implementation that avoids quadratic time for the most obvious case, i.e. All equal elements should be distributed elements equal to the rotation between the parts rationally.

Possible options:

• The middle part includes only 1 element: the arch. In this case, pivot takes its last place in the array after the partition and will not be used in recursive calls. This is what you had in mind when the consolidation point took its place in the iteration. For this approach, a good implementation should move about half the elements, equal to the rotation to the left side, and the other to the right side, otherwise we will have quadratic time for the array with all equal elements.
• There is no middle part. The rotation and all elements equal to it are distributed between the left and right parts. This is something that is related to implementation. Once again, with this approach, about half of the elements equal to the axis of rotation should go to the left side, and the other to the right side. It can also be mixed with the first option, depending on whether we are sorting an array with an odd or even number of elements.
• Each element, equal to the axis, goes into the middle part. On the left or right side there are no elements equal to the axis of rotation. This is quite effective and that the Wikipedia example provides for solving a problem equal to all the elements. In this case, arrays with all elements equal to each other are sorted in linear time.

Thus, the correct and efficient implementation of quicksort is rather complicated (there is also the problem of choosing a good rod, for which there are also several approaches with different trade-offs or optimization of switching to another non-recursive sorting algorithm for smaller array sizes).

Also, it looks like the implementation you are connected to can make recursive calls of overlapping subarrays:

if (i <= j) { exchange(i, j); i++; j--; } 

For example, when i is equal to j , these elements will be replaced, and i will become more than j by 2. After that, 3 elements will overlap between the ranges of the following recursive calls. The code still works correctly, but.