Magic Bookof Algorithms
/
DE

SortingSRT-03

Quick Sort

One value becomes the divider, everything smaller moves to its left.

Running time
O(n log n)
Worst case
O(n²)
Extra memory
O(log n)
Stable
no

01What it is about

Quick Sort sorts without ever having to merge two halves. Instead it picks one value as the pivot and rearranges the array so that only smaller values are to its left and only bigger ones to its right.

After that the pivot already sits at its final position, and the same procedure is applied to both sides. In practice Quick Sort is usually the fastest of the classic sorting algorithms.

9471385
Everything below the pivot collects on the left, then the pivot slides into its final place.

02How it works

The heart of it is partitioning. Here the last element of the section is used as the pivot:

  1. A boundary marks the first position that still belongs to the greater part. It starts at the very left.
  2. Every element is compared with the pivot. If it is smaller or equal it is swapped to the boundary, and the boundary moves one step further.
  3. At the end the pivot itself is swapped onto the boundary.

Now everything left of the pivot is smaller and everything right of it is bigger. The pivot never has to move again. The two sections to its left and right start the whole thing over, until a section holds fewer than two elements.

03Implementation

MagicBook.Algorithms/Sorting/QuickSort.csC#
public static class QuickSort
{
    // Sorts the array in place.
    public static void Sort(int[] numbers) => Sort(numbers, 0, numbers.Length - 1);

    private static void Sort(int[] numbers, int left, int right)
    {
        // A section with fewer than two elements is already sorted.
        if (left >= right)
            return;

        var pivotIndex = Partition(numbers, left, right);

        // The pivot has reached its final position, so only the two sides are left to do.
        Sort(numbers, left, pivotIndex - 1);
        Sort(numbers, pivotIndex + 1, right);
    }

    // Moves every value that is smaller than the pivot to the left of it
    // and returns the position the pivot ends up at.
    private static int Partition(int[] numbers, int left, int right)
    {
        var pivot = numbers[right]; // the last element of the section serves as the pivot
        var boundary = left;        // first slot that belongs to the "greater than pivot" part

        for (var i = left; i < right; i++)
        {
            if (numbers[i] > pivot)
                continue;

            (numbers[i], numbers[boundary]) = (numbers[boundary], numbers[i]);
            boundary++;
        }

        // Finally the pivot itself is swapped onto the boundary.
        (numbers[right], numbers[boundary]) = (numbers[boundary], numbers[right]);

        return boundary;
    }
}

04Example

MagicBook.Console/Examples/QuickSortExample.csC#
var numbers = new[] { 9, 4, 7, 1, 3, 8, 2 };

QuickSort.Sort(numbers);

Console.WriteLine(string.Join(", ", numbers));
Console output
1, 2, 3, 4, 7, 8, 9

05Good to know

  • The running time depends on the pivot. If it splits the array roughly in the middle every time, the result is O(n log n). If it always hits the largest value, it degenerates to O(n²).
  • That is exactly what happens with already sorted data when you stubbornly take the last element as done here. Real implementations therefore pick the pivot at random or as the median of three candidates.
  • Quick Sort is not stable: swapping across larger distances can change the order of equal values.