if( left + 10 <= right)
{
int i = left, j = right - 1;
for ( ; ; )
{
while (a[++i] < pivot ) {} // move the left finger
while (pivot < a[--j] ) {} // move the right finger
if (i < j) swap (a[i],a[j]); // swap
else break; // break if fingers have crossed
}
swap (a[i], a[right-1]); // restore the pivot
quicksort ( a, left, i-1); // call quicksort for the left part
quicksort (a, i+1, right); // call quicksort for the left part
}
else insertionsort (a, left, right);
Let's see how this code will work on an example,
disregarding the first if statement - the check for
the number of elements.Source array to be sorted: 10, 3, 25, 6, 8, 17, 1, 2, 18, 5 I. Compute the first partitioning:
- Choosing the pivot:
- Order the three elements and hide the pivot :
- Start rearranging:
- Bring back the pivot: The pivot is swapped with a[i]
5, 3, 25, 6, 18, 17, 1, 2, 8, 10
i = left (i.e. i = 0)
j = right -1 (i.e. j = 8)
5, 3, 25, 6, 18, 17, 1, 2, 8, 10
^ ^
i j
At each run of the for loop we swap two elements3.1. First run: while (a[++i] < pivot ){}
Move i to the right skipping elements that are less than the pivot
We know that the very first element is less than the pivot, so we do not compare it
5, 3, 25, 6, 18, 17, 1, 2, 8, 10
^ ^
i j
i stops at 25, as 25 is greater than the pivot ( i = 2)We do not process the pivot, that is why we write --j - first decrement, and then compare.
5, 3, 25, 6, 18, 17, 1, 2, 8, 10
^ ^
i j
j stops at 2 , the first element from right to left that
is smaller than 8. (j = 7)else break;
5, 3, 2, 6, 18, 17, 1, 25, 8, 10
^ ^
i j
5, 3, 2, 6, 18, 17, 1, 25, 8, 10
^ ^
i j
We start with i = 2 , pointing to 2, and j = 7, pointing to 25
5, 3, 2, 6, 18, 17, 1, 25, 8, 10
^ ^
i j
5, 3, 2, 6, 18, 17, 1, 25, 8, 10
^ ^
i j
else break;
5, 3, 2, 6, 1, 17, 18, 25, 8, 10
^ ^
i j
We start with i = 4 , pointing to 1, and j = 6, pointing to 18.
5, 3, 2, 6, 1, 17, 18, 25, 8, 10
^ ^
i j
5, 3, 2, 6, 1, 17, 18, 25, 8, 10
^ ^
j i
else break;
- Choosing the pivot: the median of three: 5, 2, 1:
- Order the three elements and hide the pivot:
- Start the for loop.
- i will stop at 3 ( i = 1) - the first element greater than the pivot:
- j will stop at 1 (j = 0)- the first element from right to left smaller than the pivot. No swap is done, as i and j have crossed:
- Bring back the pivot: swap the pivot with a[1] 1, 2, 6, 3, 5
The partitioning now is:
In practice, we stop partitioning when the elements are small in number, e.g. n < 10,
and we sort with insertion sort. Here we stop at 1, for the sake of the example.
Next comes the right array: [ 6, 3, 5]
It is only of three elements, and the median of three choice will put them in order:
After it has been sorted, we will obtain:
