The Quicksort sorting algorithm can be used to efficiently sort lists and arrays. The algorithm is recursive and in each recursion step the elements are re-sorted on the basis of a so-called pivot element. A pivot element is an element which is selected at the beginning of the algorithm and which has a special meaning for the algorithm.
How it works
Basic idea:
When the Quicksort algorithm is called, first one of the elements in the array is set as the pivot element. Then the array is reordered so that the pivot element is at its final position and all elements smaller than the pivot element are inserted to the left of the pivot element and all elements larger than the pivot element are inserted to the right. Whether elements that are the same size as the pivot element are inserted to the left or right of the pivot element does not matter. Then Quicksort is recursively applied to both the subarray to the left of the pivot element and the subarray to the right of the pivot element.
Suppose the following array is to be sorted with Quicksort:
Now, as an example, if the 5 on the far right of the array is selected as the pivot element, the array will be reordered as follows:
The 5 is now at its final position. Quicksort is then called on the subarray from index 0 to 3 and then on the subarray with indices 5 to 7.
Pseudocode:
Procedure:
In addition to the array, the algorithm also receives the index of the leftmost and rightmost elements of the subarray that is to be sorted with Quicksort. If the subarray contains only one element or no element, the execution of the current function call can be aborted, because arrays with less than 2 elements are sorted automatically.
At the beginning, a pivot element is selected. In the above code, the right element is always selected as the pivot element. However, any element in the subarray could be selected as a pivot element (section: Choice of the pivot element:). Also, 2 variables i and j are defined. i is assigned the index of the leftmost element in the array and j is assigned the index of the element to the left of the pivot element.
Now the index i is shifted to the right until either an element is found which is larger than the pivot element or until j is reached. Then, j is shifted to the left until an element is found that is smaller than the pivot element or until i is reached. If both i is found to be larger than the pivot element and j is found to be smaller than the pivot element, they are swapped. This is done until i and j point to the same field.
Apart from the pivot element, there is now a range in the subarray where all elements smaller than the pivot element are located, followed by a subrange where all elements larger than the pivot element are located. Elements equal to the pivot element are either in one or the other range.
If there are elements in the subarray that are larger than the pivot element, then after the loop, i points to the leftmost field in the range where the elements are larger than the pivot element. This is because i is used to find a larger element before j is used to find a smaller element. In this case, the pivot element must be swapped with the element with index i.
If there are no elements in the subarray that are larger than the pivot element, then after the loop i points to the field to the left of the pivot element and the element in that field is smaller than the pivot element. In this case, the pivot element is already in the right position and does not need to be swapped.
Then Quicksort is called with the subarray to the left of the pivot element and then with the subarray to the right of the pivot element.
Example:
As an example, the array from above is to be sorted. The right element is always selected as the pivot element.
Function call Quicksort(A, 0, 7):
The quicksort algorithm is called with index 0 as left bound and index 7 as right bound. The pivot element 5 is selected. i points to the first element and j to the element to the left of the pivot element.
4 and 2 are both smaller than the pivot element, so i is moved 2 times 1 field further to the right. 6 is larger than 5, so i stays at 6.
Now the number at position j is examined. The 8 is larger than the 5 and therefore j is moved one field to the left.
Since the 3 is smaller than the 5, j stops at the 3. Now the 6 and the 3 are swapped.
Now the element at position i is again compared with the pivot element. 3 is smaller than 5, so i is moved 1 further to the right. 7 is greater than 5 and therefore i remains at 7.
Then j is compared with the pivot element. 6 is greater than 5, so j is set 1 further to the left. 1 is smaller than 5, so j remains at 1.
The numbers in fields i and j are swapped again.
Again, the number at position i is compared with the pivot element. Since 1 is smaller, i is set one field further to the right.
i and j now point to the same field. So the loops are canceled.
In the fields 0 to 3 the elements are now smaller than 5 and in the fields 4 to 6 larger. Now the element at position i (i.e. 7) is swapped with the pivot element.
The 5 is now at the final position and all elements to the left of it are smaller and all elements to the right of it are larger.
Next, Quicksort is called with the left subarray and when this call is processed Quicksort is called with the right subarray.
Function call Quicksort(A, 0, 3):
Again the right element is selected as pivot element. i is set to the left element and j to the element left of the pivot element.
The 4 is larger than the pivot element and therefore i remains at the 4. Since all elements between j and i are larger than 1, j is moved 3 times 1 field further to the left until it is on the same field as i. After that, all loops are aborted.
Again, the pivot element is swapped with the element at location i.
The 1 is now at the final position, too. Next, Quicksort(A, 0, -1) and then Quicksort(A, 1, 3) are called.
Function call Quicksort(A, 0, -1):
This call is aborted because the left index is not smaller than the right index.
Result:
After the call of Quicksort(A, 0, -1) Quicksort(A, 1, 3) is called. When this call is processed, the call Quicksort(A, 5, 7) from the first call is processed. Since this is very redundant and would go completely beyond the scope, I will abbreviate this and show the result directly:
Choice of the pivot element:
Until now, only the right element from the subarray was selected as the pivot element. In principle, however, any other element from the subarray could also be selected. For example, the element in the middle is also a popular choice. In this case, however, the pivot element should be swapped with the right element before i and j are initialized.
But why should you make this extra effort? The quicksort algorithm becomes particularly efficient if there are a similar number of elements on both sides of the pivot element after the reordering. If always the right element is chosen as pivot element and if the array to be sorted is already sorted, then after the re-sort all elements remain to the left of the pivot element. In this case, the runtime complexity is quadratic.
To prevent this, if the array is partially presorted, you should choose the middle element or a random element as the pivot element.