Quick Sort

QuickSort, also known as partition-exchange sort, is a highly efficient, comparison-based sorting algorithm. Originally developed by Tony Hoare in 1960 during his work on machine language translation, it operates on a divide et impera strategy.

It selects a pivot element from the array and partitions the remaining elements into two groups: those less than the pivot and those greater than the pivot. This process is recursively applied to the two partitions, breaking down a large sorting problem into smaller, more manageable ones until the entire array is sorted.

Over the years, QuickSort has firmly established its status as a commonly used sorting algorithm in the software industry.

How it works

It operates on the following key points:

• Pivot selection: Initially, the algorithm chooses a pivot element from the array. The pivot can be chosen randomly or through a specific strategy, often it's the first, middle, or last element.
• Partitioning: Post pivot selection, the array is rearranged such that all elements smaller than the pivot are moved before it and all elements larger are moved after it. This process is referred to as partitioning. Upon the completion of this step, the pivot element is in its final position in the sorted array.
• Recursion: The algorithm then recursively applies the same operations to the two partitions, i.e., the elements less than the pivot and those greater than the pivot. This process continues, recursively dividing the array until only one element remains in each partition. At this stage, since each single-element array is inherently sorted, the entire array becomes sorted.

Here is a simple implementation in C#:

public void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        var pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);  
        QuickSort(arr, pivot + 1, right); 
    }
}

public int Partition(int[] arr, int left, int right)
{
    var pivot = arr[right];  
    var i = left - 1;

    for (var j = left; j <= right - 1; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(ref arr[i], ref arr[j]);
        }
    }

    Swap(ref arr[i + 1], ref arr[right]);
    return i + 1;
}

public void Swap(ref int a, ref int b)
{
    (a, b) = (b, a);
}

To use the above implementation, you simply need to call the QuickSort method with your array and the lowest and highest indexes as arguments. For instance, if an array of integers is known as arr, the sorting process would be initiated by executing the corresponding method call:

QuickSort(arr, 0, arr.Length - 1);

Time complexity

The time complexity in the best and average case is O(n log n) making it a compulsory choice for large data sets. In the worst-case scenario, that is, when the input array is already sorted, its time complexity becomes O(n²).

Space complexity

The space complexity is O(log n). This mirrors the space required to accommodate the stack of recursive calls. However, it is worth mentioning that this can vary depending on the intricacies of the implementation and the pivot selection strategy. Generally, it performs impressively in terms of space complexity, making it a good choice when memory is a consideration.

Conclusion

QuickSort is a highly effective and adaptable sorting algorithm that is extensively used when dealing with large datasets. Its performance may taper in certain edge cases, but overall, it delivers an excellent balance of time and space efficiency, making it a preferred choice across a range of data management scenarios.

References

• Algoritmi e programmazione in C di Francesco Oliveri, Aracne editrice (Italian book)