Quick S

Sorting Algorithms - QUICKSORT

---

Example

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:
Source array: 10, 3, 25, 6, 8, 17, 1, 2, 18, 5

1. Choosing the pivot:
The median-of-three: [10, 8, 5] : the median is 8

2. Order the three elements and hide the pivot :
5, 3, 25, 6, 8, 17, 1, 2, 18, 10
5, 3, 25, 6, 18, 17, 1, 2, 8, 10

3. Start rearranging:
Set two indices: i and j
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 elements
3.1. First run: while (a[++i] < pivot ){}
++i means: first increment i, then perform the comparison.
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)
while (pivot < a[--j] ) {}
Initially j is 'right'-1 = 8. This is the pivot.
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)
if (i < j) swap (a[i], a[j]);
else break;
i = 2 is less than j=7 and we swap 25 and 2:


5, 3, 2, 6, 18, 17, 1, 25, 8, 10
      ^                 ^
      i                 j

3.2. Second run of the for loop:


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
while (a[++i] < pivot) {}
6 is less then the pivot (8), we skip it, and i stops at 18 ( i = 4)


5, 3, 2, 6, 18, 17, 1, 25, 8, 10
             ^         ^
             i         j

while (pivot < a[--j]) {}
1 is less than the pivot, j stops there. (j = 6)


5, 3, 2, 6, 18, 17, 1, 25, 8, 10
             ^      ^
             i      j

if (i < j) swap (a[i], a[j]);
else break;
i = 4 is less than j = 6 and we swap 18 and 1:


5, 3, 2, 6, 1, 17, 18, 25, 8, 10
            ^       ^
            i       j

3.3. Third run of the for loop:
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

while (a[++i] < pivot {}
17 is greater than the pivot and i stops there (i = 5)
while (pivot < a[--j] < {}
1 is less then the pivot and j stops there ( j = 4)


5, 3, 2, 6, 1, 17, 18, 25, 8, 10
            ^   ^
            j   i

if (i < j) swap (a[i], a[j]);
else break;
Now we break, because i and j have crossed

4. Bring back the pivot:
The pivot is swapped with a[i]
5, 3, 2, 6, 1, 8, 18, 25, 17, 10
This is the first partitioning:
[ 5, 3, 2, 6, 1 ] [8] [18, 25, 17, 10]

II. Recursively we process the left part of the array: 5, 3, 2, 6, 1

1. Choosing the pivot: the median of three: 5, 2, 1:
The median is 2

2. Order the three elements and hide the pivot:
1, 3, 6, 2, 5

3. Start the for loop.
1. i will stop at 3 ( i = 1) - the first element greater than the pivot:
2. 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:
4. Bring back the pivot: swap the pivot with a[1]
1, 2, 6, 3, 5
The partitioning now is:
[ 1 ] [ 2 ] [ 6, 3, 5 ]

III. Do the same with the left array and the right array.
The left array consists only of one element, so we stop.
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:
3, 5, 6
Now we have a sorted part: 1, 2, 3, 5, 6
IV. In a similar way we process the right part in the first partitioning: 18, 25, 17, 10.
After it has been sorted, we will obtain:
[1, 2, 3, 5, 6] [8] [10, 17, 18, 25] and this is the whole array sorted.