QuickSort - Eishaaya/GMRDataStructuresTest GitHub Wiki

Sorting by partitioning

The goal of quick sort is to select a pivot variable and sort all elements smaller than it into the lower half and all elements larger than it into the larger half. As such:

Similar to merge sort, quick sort will then perform the sorting algorithm on each half the collection until the whole collection is sorted. The advantage that quick Sort has over merge sort is that it does not have to duplicate the set in order to sort. The entire algorithm occurs in-place in memory, with a trivial amount of auxiliary storage needed for the recursive calls O(log n) (in comparison to input size of n) and O(n) in worst case scenario for the naïve implementation.

Some might say that quick sort is not "in-place" algorithm due to it using a minimum of O(log n) space for the recursive calls; however, most refer to "in-place" as additional storage on the heap memory, i.e., what you must explicitly allocate for the algorithm to work.

Quick sort has a worst-case complexity of O(n^2), but, it is actually very rare for that to happen on a randomized list. Instead, most judge quick sort by its average-case complexity of O(n log n).

Implementation Guide:

Quick sort works by partitioning an array into two sub-sections based on a pivot value. How you select the pivot value is not important since, in a random array, any index selection will result in a random pivot value. The simplest way is to either select the first or last index. Next, since the method of swapping the values differs from one programmer to another, we will describe the two most popular methods:

Lomuto Partition

In this method we select a pivot from the end of the array and set a "wall" (integer value representing index) at the beginning. We then proceed to iterate through the array, swapping any values that are less than the pivot to the left side of the wall while ignoring any values that are greater than the pivot. To move a value to the left side of the wall, we swap the value that we found to be smaller than the pivot with the index that is just to the right of the wall then increase the index of the wall. We continue doing so until we reach the end of the array and then place the pivot at the wall location. The algorithm is then repeated recursively on both sides of the wall but neither side including the pivot.

Here is an example:

Hoare Partition

In this method we select a pivot from the beginning of the array and set two indicators for the ends of the array. Let's call the indicator at the beginning 'LEFT' and the indicator at the end 'RIGHT'.

We then proceed to move the LEFT indicator forward while the value at the LEFT indicator is less than the pivot. Once a value is found that is equal to or greater than the pivot, we proceed to the RIGHT indicator. We move the RIGHT indicator back while the value at the RIGHT indicator is greater than the pivot. Once a value is found that is equal to or less than the pivot we stop.

Now we swap the values at the LEFT and RIGHT indicators,

then continue moving them as described as before. Moving each indicator at least once, starting with the LEFT indicator first, then the RIGHT. We continue moving and swapping until the LEFT and RIGHT indicators pass each other.

Once the LEFT and RIGHT indicators pass or meet each other, we split the array at the RIGHT indicator and the algorithm is then repeated recursively on both sides. The element pointed to by the RIGHT indicator will be included in the LEFT sub array. Unlike the Lomuto partition, the pivot is not fully sorted, and is therefore included in the next recursive iteration of the sort.

Applications:

Although having the same growth, quick sort is better than merge sort by a multiplicative factor and is a great choice if stability is not a concern. It performs poorly when the number of unique keys are small or if the data is nearly sorted. In many cases a 3-way partition is used. Sorting with quick sort is done in-place, and therefore it is a better option than merge sort when memory is a concern. In-place algorithms manipulate data without copying it. This is not the case for merge sort, as it needs to copy data into a temporary array before the merging takes place.

References

<-- Previous | Next -->