MARCIN.com

The quicksort is a representative of the divide and conquer algorithms and divides a problem into a set of smaller ones. It picks some value (e.g., from the last element of the array) as a pivot. Then, it reorders the array in such a way that values lower than the pivot are placed before it (lower subarray), while values greater than or equal to the pivot are placed after it (higher subarray). Such a process is called partitioning. Next, the algorithm recursively sorts each of the afore mentioned subarrays. Each subarray is further divided into the next two subarrays, and so on. The recursive calls stop when there are one or zero elements in a subarray, because in such a case there is nothing to sort.

The code is as follows:

void Sort(int[] a)
{
    Sort(a, 0, a.Length - 1);
}

The most important part of code is shown below:

void Sort(int[] a, int l, int u)
{
    if (l >= u) { return; }

    int pivot = a[u];
    int j = l - 1;
    for (int i = l; i < u; i++)
    {
        if (a[i] < pivot) { Swap(a, ++j, i); }
    }

    int p = j + 1;
    (array[p], array[u]) = (array[u], array[p]);

    Sort(a, l, p - 1);
    Sort(a, p + 1, u);
}

This entry can contain content, including parts of code, from one of my books, namely from the Second Edition of C# Data Structures and Algorithms, published by Packt Publishing in 2024. If you want to read more about the quicksort algorithm, as well as about other kinds of sorting algorithms, I encourage you to take a look at the mentioned book. You can buy it here.

The content, including any part of code, is presented without warranty, either express or implied. The author cannot be held liable for any damages caused or alleged to have been caused directly or indirectly by any content shown on this website.