Quicksort

Quicksort is a divide-and-conquer algorithm that sorts an array by selecting a « pivot » element and partitioning the other elements into two groups, those less than the pivot and those greater than the pivot.

It then recursively sorts the sub-arrays on either side of the pivot. The pivot is typically chosen as the last element in the array, but other methods such as choosing a random element or the median can also be used.

The key step in the Quicksort algorithm is the partitioning process, which rearranges the array in such a way that all elements less than the pivot come before all elements greater than the pivot. This partitioning process can be done in linear time, making Quicksort an efficient algorithm with an average time complexity of O(n log n).

When using Quicksort ?

Quicksort is a popular sorting algorithm for a number of reasons:

1. It has a relatively low average time complexity of O(n log n), making it efficient for large data sets.
2. It is an in-place sorting algorithm, meaning it does not require additional memory space to sort the data.
3. It is a comparison-based sorting algorithm, which means that it can be used to sort data of any type for which a comparison operator (i.e. < or >) is defined.
4. It is easily implemented and understood

Because of these reasons, Quicksort is often used as the default sorting algorithm in many libraries and programming languages. It is also used in many real-world applications such as sorting large data sets in databases and data warehouses.

It’s important to note that quicksort has worst case time complexity of O(n^2) which can occur in the case of worst pivot selection, so it’s recommended to use randomized quicksort to avoid worst case scenarios.

How it’s works ?

Quicksort works by selecting a « pivot » element from the array and partitioning the other elements into two groups: those less than the pivot and those greater than the pivot. It then recursively sorts the sub-arrays on either side of the pivot. The pivot is typically chosen as the last element in the array, but other methods such as choosing a random element or the median can also be used.

The algorithm proceeds as follow:

1. Choose a pivot element from the array.
2. Partition the array so that all elements less than the pivot come before all elements greater than the pivot.
3. Recursively apply the Quicksort algorithm to the sub-arrays on either side of the pivot.
4. Once the sub-arrays are sorted, the pivot element is in its correct position in the final sorted array.
5. The process continue until all sub-arrays are sorted.

Pseudo Code

procedure quicksort(A, lo, hi) is
    if lo < hi then
        pivot := partition(A, lo, hi)
        quicksort(A, lo, pivot)
        quicksort(A, pivot + 1, hi)

procedure partition(A, lo, hi) is
    pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j - 1
        while A[j] > pivot

        if i >= j then
            return j

        swap A[i] with A[j]

Here is a breakdown of what is happening in the code:

• QUICKSORT function takes in three parameters: an array A, a lower bound low, and an upper bound high.It checks if the lower bound is less than the upper bound, and if so, it proceeds to partition the array between these bounds.
• PARTITION function is called, which selects the pivot element (in this case, the last element of the array) and rearranges the elements of the array so that all elements less than the pivot come before all elements greater than the pivot. It returns the pivot index.
• Then the quicksort function is called recursively on the sub-arrays on either side of the pivot (the sub-array before the pivot and the sub-array after the pivot)
• The process continues recursively until all sub-arrays have been sorted.

Please note that the above pseudo code is a basic implementation of quicksort, there are many variations and optimizations that can be done to improve the performance.

Here some of several ways to optimize the algorithm :

1. Using a median-of-three method to choose the pivot element, where the pivot is chosen as the median of the first, middle, and last elements of the array. This helps to avoid worst-case scenarios where the pivot is chosen as the smallest or largest element in the array.
2. Using randomized pivot selection, where the pivot is chosen at random. This also helps to avoid worst-case scenarios.
3. Using a small cutoff value to switch to insertion sort when the sub-array size becomes small. Insertion sort is more efficient for small arrays.
4. Using a technique called « tail-call optimization » to reduce the amount of stack space used by the recursive calls.
5. Avoiding unnecessary swaps, for example by using a dual-pointer technique.
6. Using a three-way partitioning scheme, which is useful for arrays with many duplicate values.
7. Optimizing the algorithm to work with cache memory and modern computer architectures
8. Using multi-threading and parallelism to speed up the sorting process.

It’s worth noting that quicksort is very sensitive to the pivot selection, as it affects the time complexity of the algorithm. So, choosing a good pivot can have a significant impact on the performance of the algorithm.

Let’s do it in C#

 public class QuickSort
 {

        public static void SortArray(int[] array, int left, int right)
        {
            if (left < right)
            {
                int pivot = Partition(array, left, right);

                if (pivot > 1)
                {
                    SortArray(array, left, pivot - 1);
                }
                if (pivot + 1 < right)
                {
                    SortArray(array, pivot + 1, right);
                }
            }
        }

        public static int Partition(int[] array, int left, int right)
        {
            int pivot = array[left];
            while (true)
            {
                while (array[left] < pivot)
                {
                    left++;
                }

                while (array[right] > pivot)
                {
                    right--;
                }

                if (left < right)
                {
                    if (array[left] == array[right]) return right;
                    int temp = array[left];
                    array[left] = array[right];
                    array[right] = temp;
                }
                else
                {
                    return right;
                }
            }
        }
    }

This implementation uses the « recursive » approach to quicksort, where the SortArray method calls itself with different partitions of the array until the array is fully sorted.

The Partition method is used to select a pivot value and partition the array so that all elements less than the pivot are on the left and all elements greater than the pivot are on the right.

Note that there are different ways to pick the pivot element, the code above is using the first element of the array as pivot but the « median of three » or « randomized pivot » techniques can be used to avoid worst case performance.

Also keep in mind that quicksort is usually implemented as an in-place sorting algorithm, which means that it sorts the array without using additional memory.