Quicksort algorithm is one of the most popular sorting algorithms in use out there. In case you haven’t heard for it before, we can also call it divide and conquer algorithm. Furthermore, as it’s name suggests, it divides arrays into partitions and sorts them and objects inside.

Unlike sorting algorithms I’ve covered so far on this blog, quicksort algorithm sorts objects with best efficiency among them all. And in order to be this way, we don’t need to sacrifice any other aspect of it as it is also pretty simple to understand.

Now let’s dive into details on how exactly does it work. First of all, algorithm picks a value from the array and sets it as a pivot. Next, it reorganizes the array in such a way that all values lower than the pivot are placed before it and higher after it.

In doing so, we form lower and higher subarray, on which we repeat this whole operation recursively. Therefore, we need to stop the recursion when there is only 1 or no elements inside the subarray we want to sort.

Quicksort algorithm in C#

Since the process utilizes recursion, this makes it way more efficient than other sorting algorithms I’ve covered so far. In case you’re not familiar what it is, it’s basically calling a method inside the same method. A little mindbending, but nothing we can’t clear up with implementation in code.

So let’s take a look at how it works in practice.

public static class Quicksort
    {
        public static void Sort<T>(T[] array) where T : IComparable
        {
            Sort(array, 0, array.Length - 1);
        }

        private static T[] Sort<T>(T[] array, int lower, int higher) where T : IComparable
        {
            if (lower < higher)
            {
                int p = Partition(array, lower, higher);
                Sort(array, lower, p);
                Sort(array, p + 1, higher);
            }
            return array;
        }

        private static int Partition<T>(T[] array, int lower, int higher) where T : IComparable
        {
            int i = lower;
            int j = higher;
            T pivot = array[lower];
            do
            {
                while (array[i].CompareTo(pivot) < 0)
                {
                    i++;
                }
                while (array[j].CompareTo(pivot) > 0)
                {
                    j--;
                }
                if (i >= j)
                {
                    break;
                }
                Swap(array, i, j);

            } while (i <= j);
            return j;

        }

        private static void Swap<T>(T[] array, int first, int second)
        {
            T temp = array[first];
            array[first] = array[second];
            array[second] = temp;
        }
    }

As you can see from the code above, we created a public static class Quicksort, which holds 4 methods in total. However, only 1 is public while others are private. Therefore, private methods only serve as individual components of the entire process.

For versatility, we can use IComparable inteface which holds method CompareTo. Furthermore, this method is compatible with various different data types. Therefore, we’ll use a generic data type T when we’re declaring methods.

First of all, the Swap method just swaps 2 objects of the array, which takes 3 arguments, the array and indexes of objects.

Next, the Partition method swaps the objects around the pivot object and returns object index at which we divide the array into subarrays.

Third private method is an overloaded Sort method, which utilizes Partition method and itself to recursively sort the subarrays.

And finally, the public Sort method, which takes only one argument, the array. We call the private Sort method inside it, where we also set all 3 arguments that it needs.

Conclusion

I hope this guide helped you gain a better understanding of how a Quicksort algorithm works in C#.

In case you want to see it in action, you can also download the demo project and try it out for yourself.