The QuickSort Algorithm

As one of the more advanced sorting algorithms, you might think that the Quicksort Algorithm is steeped in complicated theoretical background, but this is not so. Like Insertion Sort, this algorithm has a fairly simple concept at the core, but is made complicated by the constraints of the array structure.

The basic concept is to pick one of the elements in the array as a pivot value around which the other elements will be rearranged. Everything less than the pivot is moved left of the pivot (into the left partition). Similarly, everything greater than the pivot goes into the right partition. At this point each partition is recursively quicksorted.

The Quicksort algorithm is fastest when the median of the array is chosen as the pivot value. That is because the resulting partitions are of very similar size. Each partition splits itself in two and thus the base case is reached very quickly.

In practice, the Quicksort algorithm becomes very slow when the array passed to it is already close to being sorted. Because there is no efficient way for the computer to find the median element to use as the pivot, the first element of the array is used as the pivot. So when the array is almost sorted, Quicksort doesn't partition it equally. Instead, the partitions are lopsided like in Figure 2. This means that one of the recursion branches is much deeper than the other, and causes execution time to go up. Thus, it is said that the more random the arrangement of the array, the faster the Quicksort Algorithm finishes.


Figure 1: The ideal Quicksort on a random array.


Figure 2: Quicksort on an already sorted array.


These are the steps taken to sort an array using QuickSort:

Elements in red indicate swaps.
Elements in blue indicate comparisons.
Special commentary is in green.

3 1 4 5 9 2 6 8 7 
Calling quickSort on elements 0 to 8	
Definitions: a "small" element is one whose value is less than
or equal to the value of the pivot. Likewise, a "large" element
is one whose value is larger than that of the pivot.
 At the beginning, the entire array is passed into the quicksort 
function and is essentially treated as one large partition.
 At this time, two indices are initialized: the left-to-right
search index, i, and the right-to-left search index, k. The value
of i is the index of the first element in the partition, in this 
case 0, and the value of k is 8, the index of the last element in
the partition. The relevance of these variables will be made apparent 
in the code below.					

3 1 4 5 9 2 6 8 7
 The first element in the partition, 3, is chosen as the pivot
element, around which two subpartitions will be created. The end
goal is to have all the small elements at the front of the partition,
in no particular order, followed by the pivot, followed by the large
elements.
 To do this, quicksort will scan rightwards for the first large 
element. Once this is found, it will look for the first small
element from the right. These two will then be swapped.
 Since i is currently set to zero, the pivot is actually compared
to itself in the search of the first large element.
3 1 4 5 9 2 6 8 7
 The search for the first large element continues rightwards. The 
value of i gets incremented as the search moves to the right.

3 1 4 5 9 2 6 8 7
 Since 4 is greater than the pivot, the rightwards search
stops here. Thus the value of i remains 2.

3 1 4 5 9 2 6 8 7 
 Now, starting from the right end of the array, quicksort searches
for the first small element. And so k is decremented with each
step leftwards through the partition.

3 1 4 5 9 2 6 8 7
3 1 4 5 9 2 6 8 7
3 1 4 5 9 2 6 8 7
 Since 2 is not greater than the pivot, the leftwards search can stop. 

3 1 2 5 9 4 6 8 7
 Now elements 4 and 2 (at positions 2 and 5, respectively) are swapped.

3 1 2 5 9 4 6 8 7
 Next, the rightwards search resumes where it left off: at position 2, which
is stored in the index i.

3 1 2 5 9 4 6 8 7
 Immediately a large element is found, and the rightwards search stops
with i being equal to 3.

3 1 2 5 9 4 6 8 7
 Next the leftwards search, too, resumes where it left off: k was 5
so the element at position 5 is compared to the pivot before k
is decremented again in search of a small element.

3 1 2 5 9 4 6 8 7
 This continues without any matches for some time... 

3 1 2 5 9 4 6 8 7 	 
3 1 2 5 9 4 6 8 7
  The small element is finally found, but no swap is performed since
at this stage, i is equal to k. This means that all the small
elements are on one side of the partition and all the large elements are 
on the other.

2 1 3 5 9 4 6 8 7
  Only one thing remains to be done: the pivot is swapped with the element
currently at i. This is acceptable within the algorithm because it
only matters that the small element be to the left of the pivot, but their
respective order doesn't matter. Now, elements 0 to (i - 1) form the
left partition (containing all small elements) and elements k + 1 onward
form the right partition (containing all large elements.
Calling quickSort on elements 0 to 1
 The right partition is passed into the quicksort function.

2 1 3 5 9 4 6 8 7
 2 is chosen as the pivot. 
It is also compared to itself in the search for a small element within 
the partition.

2 1 3 5 9 4 6 8 7
 The first, and in this case only, small element is found.

2 1 3 5 9 4 6 8 7
 Since the partition has only two elements, the leftwards search
begins at the second element and finds 1.

1 2 3 5 9 4 6 8 7
 The only swap to be made is actually the final step where the pivot
is inserted between the two partitions. In this case, the left partition 
has only one element and the right partition has zero elements.

Calling quickSort on elements 0 to 0
 Now that the left partition of the partition above is quicksorted:
there is nothing else to be done

Calling quickSort on elements 2 to 1
 The right partition of the partition above is quicksorted.
In this case the starting index is greater than the ending index due to the
way these are generated: the right partition starts one past the pivot
of its parent partition and goes until the last element of the parent
partition. So if the parent partition is empty, the indices generated
will be out of bounds, and thus no quicksorting will take place.

Calling quickSort on elements 3 to 8
The right partition of the entire array is now being quicksorted
5 is chosen as the pivot.

1 2 3 5 9 4 6 8 7
1 2 3 5 9 4 6 8 7
The rightwards scan for a large element is initiated.
9 is immediately found.

1 2 3 5 9 4 6 8 7 
Thus, the leftwards search for a small element begins...

1 2 3 5 9 4 6 8 7
1 2 3 5 9 4 6 8 7
1 2 3 5 9 4 6 8 7
At last, 4 is found. Note k = 5.

1 2 3 5 4 9 6 8 7
 Thus the first large and small elements to be found are swapped.

1 2 3 5 4 9 6 8 7
The rightwards search for a large element begins anew.

1 2 3 5 4 9 6 8 7
Now that it has been found, the rightward search can stop.

1 2 3 5 4 9 6 8 7
Since k was stopped at 5, this is the index from which the
leftward search resumes. 

1 2 3 5 4 9 6 8 7
1 2 3 4 5 9 6 8 7
 The last step for this partition is moving the pivot into the right spot.
Thus the left partition consists only of the element at 3 and the right partition is
spans positions 5 to 8 inclusive. 

Calling quickSort on elements 3 to 3
 The left partition is quicksorted (although nothing is done. 

Calling quickSort on elements 5 to 8
 The right partition is now passed into the quicksort function. 

1 2 3 4 5 9 6 8 7
 9 is chosen as the pivot. 

1 2 3 4 5 9 6 8 7
 The rightward search for a large element begins. 

1 2 3 4 5 9 6 8 7			
1 2 3 4 5 9 6 8 7 
 No large element is found. The search stops at the end of the partition.

1 2 3 4 5 9 6 8 7 
 The leftwards search for a small element begins, but does not continue
since the search indices i and k have crossed. 

1 2 3 4 5 7 6 8 9 
 The pivot is swapped with the element at the position k: this is
the last step in splitting this partition into left and right subpartitions.
Calling quickSort on elements 5 to 7
 The left partition is passed into the quicksort function. 

1 2 3 4 5 7 6 8 9
 6 is chosen as the pivot. 

1 2 3 4 5 7 6 8 9
 The rightwards search for a large element begins from the left
end of the partition. 

1 2 3 4 5 7 6 8 9
 The rightwards search stops as 8 is found. 

1 2 3 4 5 7 6 8 9
 The leftwards search for a small element begins from the right 
end of the partition. 

1 2 3 4 5 7 6 8 9
 Now that 6 is found, the leftwards search stops. As the search
indices have already crossed, no swap is performed. 

1 2 3 4 5 6 7 8 9
 So the pivot is swapped with the element at position k, the 
last element compared to the pivot in the leftwards search. 

Calling quickSort on elements 5 to 5
 The left subpartition is quicksorted. Nothing is done since it is too small. 

Calling quickSort on elements 7 to 7
 Likewise with the right subpartition. 

Calling quickSort on elements 9 to 8
 Due to the "sort the partition startitng one to the right of the pivot"
construction of the algorithm, an empty partition is passed into the quicksort
function. Nothing is done for this base case.

1 2 3 4 5 6 7 8 9
 Finally, the entire array has been sorted. 

An implementation of the algorithm is shown below:

public void quickSort(int array[]) 
// pre: array is full, all elements are non-null integers
// post: the array is sorted in ascending order
{
	quickSort(array, 0, array.length - 1);              // quicksort all the elements in the array
}


public void quickSort(int array[], int start, int end)
{
        int i = start;                          // index of left-to-right scan
        int k = end;                            // index of right-to-left scan

        if (end - start >= 1)                   // check that there are at least two elements to sort
        {
                int pivot = array[start];       // set the pivot as the first element in the partition

                while (k > i)                   // while the scan indices from left and right have not met,
                {
                        while (array[i] <= pivot && i <= end && k > i)  // from the left, look for the first
                                i++;                                    // element greater than the pivot
                        while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first
                            k--;                                        // element not greater than the pivot
                        if (k > i)                                       // if the left seekindex is still smaller than
                                swap(array, i, k);                      // the right index, swap the corresponding elements
                }
                swap(array, start, k);          // after the indices have crossed, swap the last element in
                                                // the left partition with the pivot 
                quickSort(array, start, k - 1); // quicksort the left partition
                quickSort(array, k + 1, end);   // quicksort the right partition
        }
        else    // if there is only one element in the partition, do not do any sorting
        {
                return;                     // the array is sorted, so exit
        }
}

public void swap(int array[], int index1, int index2) 
// pre: array is full and index1, index2 < array.length
// post: the values at indices 1 and 2 have been swapped
{
	int temp = array[index1];           // store the first value in a temp
	array[index1] = array[index2];      // copy the value of the second into the first
	array[index2] = temp;               // copy the value of the temp into the second
}

Written by Eugene Jitomirsky.

Improved code courtesy of Pavel.

Copyright © 2005-2014 MyCSTutorials.com