Quicksort in C#

Quicksort - overview

The quicksort algorithm is a very elegant and fast sorting algorithm. It was named "quicksort" by its originator Tony Hoare, who developed it in 1960.

Quicksort is a good example of the general problem solving heuristic divide and conquer. The basic idea of such an algorithm is to split data into two or more sub-problems and then solving the parts individually and in the end combine the part solutions to get the full solution.

The algorithm can be used to sort an array of for example integers or strings.

Description of the quicksort algorithm

The first step in the algorithm is to choose a pivot element. A simple choice could be to pick the leftmost element of the partition, or as in the C# example below to use the partitions middle index.

In the next step it places elements that are larger than the pivot on the right side of the pivot. In the same manner it then places elements that are less than or equal to the pivot on the left side.

At this stage the array is split up into two partitions and the array is sorted to some extent. All values in the right partition are larger than the all values in the left partition.

Now the algorithm can continue to apply quicksort recursively on each of the two partitions. For each partition the algorithm will pick a new pivot and then separate the values in two new smaller partitions. 

The recursion will go on until the base case is reached. The base case occurs when the arrays have been reduced to a size of 1 or zero, since that small arrays never need to be sorted.

Example of an implementation of quicksort in C#

    private void SortArrayWithQuickSort()
    {
        IComparable[] arrayToSort = new String[] { "d", "c", "r", "q", "b" };
        int minIndex = 0;
        int maxIndex = arrayToSort.Length - 1;
        Quicksort(arrayToSort, minIndex, maxIndex);

        // PrintResult(arrayToSort);
    }

    public void Quicksort(IComparable[] elements, int left, int right)
    {
        int i = left;
        int j = right;
        IComparable pivotValue = GetMiddleValue(elements, left, right);

        while (i <= j)
        {
            while (ArrayValueIsLessThanPivot(elements, i, pivotValue))
            {
                i++;
            }

            while (ArrayValueIsGreaterThanPivot(elements, j, pivotValue))
            {
                j--;
            }

            if (i <= j)
            {
                SwapValues(elements, i, j);
                i++;
                j--;
            }
        }

        if (left < j)
        {
            Quicksort(elements, left, j);
        }

        if (i < right)
        {
            Quicksort(elements, i, right);
        }
    }

    private static void SwapValues(IComparable[] elements, int i, int j)
    {
        IComparable tmp = elements[i];
        elements[i] = elements[j];
        elements[j] = tmp;
    }

    private static bool ArrayValueIsGreaterThanPivot(IComparable[] elements, 
        int j, 
        IComparable pivotValue)
    {
        return elements[j].CompareTo(pivotValue) > 0;
    }

    private static bool ArrayValueIsLessThanPivot(IComparable[] elements, 
        int i, 
        IComparable pivotValue)
    {
        return elements[i].CompareTo(pivotValue) < 0;
    }

    private static IComparable GetMiddleValue(IComparable[] elements, 
        int left, 
        int right)
    {
        int middleIndex = left + (right - left) / 2;
        return elements[middleIndex];
    }

Computational complexity

The asymptotic execution time for the quicksort algorithm is for average and best case O(n log n).
For worst case it is O(n²).