How to Implement Quick Sort in C#?

The following article describes How to Implement Quick Sort in C#.

What is Quick Sort?

It must be remembered that, Quick Sort is a divide-and-conquer algorithm for sorting an array of elements. It works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays, depending on whether they are less than or greater than the pivot. Then, the sub-arrays are sorted recursively, using the same process.

Furthermore, the algorithm has a time complexity of O(n log n) on average. Therefore, it makes it one of the fastest sorting algorithms for large data sets. However, it can be slower than other sorting algorithms in the worst-case scenario. In fact, it gives a time complexity of O(n^2) in worst-case scenario.

In other words, Quick Sort is an efficient, in-place sorting algorithm. Therefore, it is widely used in various applications, especially in embedded systems and operating systems.

Implementation of Quick Sort in C#

using System;
namespace QuickSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] myarray = { 789, 123, 90, 456, 127, 634, -778, -23, -89, 7, 34, 90, 12, -60 };
            Console.WriteLine("Array before sorting...");
            foreach (int x in myarray)
                Console.Write(x + "  ");
            Sort.QuickSort(myarray, 0, myarray.Length - 1);
            Console.WriteLine("\nArray after sorting...");
            foreach (int x in myarray)
                Console.Write(x + "  ");
            Console.WriteLine();
        }
    }
    class Sort
    {
        public static void QuickSort(int[] myarray, int low, int high)
        {
            int pivot;
            if (low < high)
            {
                Partition(myarray, low, high, out pivot);
                QuickSort(myarray, low, pivot - 1);
                QuickSort(myarray, pivot + 1, high);
            }
        }
        static void Partition(int[] a, int low, int high, out int pivot)
        {
            int i, j;
            pivot = a[high];
            i = low - 1;
            for (j = low; j <= high; j++)
            {
                if (a[j] < pivot)
                {
                    i++;
                    swap(ref a[i], ref a[j]);
                }
            }
            swap(ref a[i + 1], ref a[high]);
            pivot = i + 1;
        }
        static void swap(ref int x, ref int y)
        {
            int t = x;
            x = y;
            y = t;
        }
    }
}

Output

To summarize, the Quick Sort algorithm offers these advantages.

1. Efficient for large data sets. Evidently, Quick sort has an average time complexity of O(n log n), making it efficient for large data sets.
2. In-place sorting. Moreover, Quick sort sorts the data in the same memory space, hence requires minimal extra memory.
3. Adaptive sorting. In fact, Quick sort performs well even when the input data is partially sorted or reverse sorted.
4. Fast for small data sets. Meanwhile, Quick sort has a small overhead, making it fast for small data sets.
5. Easy to implement. Furthermore, Quick sort is relatively easy to implement compared to other sorting algorithms.
6. Quick sort can be easily parallelized for distributed computing, making it a popular choice for large scale sorting.
7. It is a comparison-based sorting algorithm and can sort elements of any type that can be compared.

Further Reading

Parameter and ParameterCollection in ADO.NET

Database Manipulation Using DataGrid

Code Render Block in ASP.NET

ASP.NET Practice Exercise

• Angular
• ASP.NET
• C
• C#
• C++
• CSS
• Dot Net Framework
• HTML
• IoT
• Java
• JavaScript
• Kotlin
• PHP
• Power Bi
• Python
• Scratch 3.0
• TypeScript
• VB.NET

Princites