Quick Sort is the consummate overachiever.  

Graduated first in his class, runs a successful business, owns a boat, married to a brilliant accountant, with two beautiful children. He does not slow down; he does everything fast and thoroughly. Keeping up with his family is quite the endeavor. When he picks something to get done, it gets DONE.

Sometimes, though, he wonders. He wonders if maybe there's more to life than climbing the org chart, buying soulless things, or making money. He wonders if maybe, just maybe, he could slow down and enjoy the scenery for once. And then he decides that's for wimps and goes back to working all hours of the night.

Photo by Wolf Zimmermann / Unsplash

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound
Project for this post: QuickSort

Algorithm

  1. SELECT a pivot point. (Our implementation selects the last number in the collection).
  2. REORDER the collection such that all values less than the pivot are before the pivot, and all values greater than the pivot are after it.
  3. RECURSIVE CONTINUE: Return to Step 1, selecting a new pivot in each of the divided higher and lower sections, until the array is sorted.

Visualization

The critical thing Quick Sort does is select a pivot point, but different varieties do this differently. In the above animation (and the below implementation), the first pivot point is merely the last item in the collection, and it continues to pick the last item in each "partition" caused by the sort as a pivot point.

Reader James Curran also contributed another visualization of this sort:

Finally, check out this audibilization on YouTube:

C# Implementation

class QuickSort
{
    static int Partition(int[] array, int low,
                                    int high)
    {
        //1. Select a pivot point.
        int pivot = array[high];

        int lowIndex = (low - 1);

        //2. Reorder the collection.
        for (int j = low; j < high; j++)
        {
            if (array[j] <= pivot)
            {
                lowIndex++;

                int temp = array[lowIndex];
                array[lowIndex] = array[j];
                array[j] = temp;
            }
        }

        int temp1 = array[lowIndex + 1];
        array[lowIndex + 1] = array[high];
        array[high] = temp1;

        return lowIndex + 1;
    }

    static void Sort(int[] array, int low, int high)
    {
        if (low < high)
        {
            int partitionIndex = Partition(array, low, high);

            //3. Recursively continue sorting the array
            Sort(array, low, partitionIndex - 1);
            Sort(array, partitionIndex + 1, high);
        }
    }

    public static void Main()
    {
        int[] array = { 72, 12, 6, 33, 81, 97, 37, 59, 52, 1, 20 };
        int length = array.Length;

        Console.WriteLine("QuickSort");
        CommonFunctions.PrintInitial(array);
        Sort(array, 0, length - 1);

        CommonFunctions.PrintFinal(array);

        Console.ReadKey();
    }
}

Time and Space Complexity

The entire reason Quick Sort has that name is because, for the vast majority of circumstances, it is demonstrably quicker than other relatively-simple implementations. That said, there is some debate about how much quicker it is than, say, Merge Sort, which clearly means that Quick Sort must get along fabulously with his father-in-law Selection Sort, but maybe not his mother-in-law.

It would be valid, I believe, to say that Quick Sort is the simplest sorting algorithm that is actually in use today for real production code. Some of the upcoming algorithms are much more complex, but faster.

Also, apropos of nothing, the inventor of Quick Sort wrote possibly my favorite adage about coding:

"There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult." - C. A. R. Hoare

Summary

Quick Sort is exactly what it sounds like. It gets things sorted, as quickly as possible, by subdividing the contents of a collection around an arbitrarily-selected pivot point. It then recursively selects smaller and smaller "partitions" and orders them.

Sometimes he wishes he could slow down. Maybe he will get his chance. Someday.

If you like pie, stick around for the next algorithm at the reunion, Heap Sort!

Heap Sort in C#
Heap Sort, the second daughter of the family, has a busy life. As the owner of a local, well-liked restaurant, Heap Sort’s Heaping Helpings,she is constantly running around trying to make her restaurant better. As themom of four kids, she (and husband Cocktail Shaker Sort) are constantly trying…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!