Quick sort program in C#

Quick sort is a widely used sorting algorithm based on the divide-and-conquer approach. It works by selecting a pivot element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. The subarrays are then recursively sorted independently. Quick sort has an average-case time complexity of O(n log n) and a worst-case time complexity of O(n^2), but its average performance is generally considered efficient.

Here's an explanation of the quick sort algorithm step by step:

1. Choose a pivot: Select an element from the array as the pivot. The choice of the pivot can affect the performance of the algorithm. Common methods include selecting the first, middle, or last element as the pivot.
2. Partition: Rearrange the elements in the array such that all elements less than the pivot are placed before it, and all elements greater than the pivot are placed after it. After partitioning, the pivot is in its final sorted position. This step ensures that the pivot is in the correct place in the final sorted array.
3. Recursion: Recursively apply the above steps to the subarrays on the left and right of the pivot. The subarray on the left contains elements smaller than the pivot, and the subarray on the right contains elements greater than the pivot.
4. Repeat: Repeat the above steps for each subarray until the entire array is sorted.

using System;

public class QuickSort
{
    public static void Main()
    {
        int[] arr = { 64, 25, 12, 22, 11 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr, 0, arr.Length - 1);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr, int low, int high)
    {
        if (low < high)
        {
            // Partition the array and get the pivot index
            int pivotIndex = Partition(arr, low, high);

            // Recursively sort the subarrays
            Sort(arr, low, pivotIndex - 1);
            Sort(arr, pivotIndex + 1, high);
        }
    }

    public static int Partition(int[] arr, int low, int high)
    {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++)
        {
            // If current element is smaller than or equal to the pivot
            if (arr[j] <= pivot)
            {
                i++;

                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i+1] and arr[high] (pivot)
        int temp2 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp2;

        return i + 1;
    }

    public static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the quick sort algorithm, and the Partition method partitions the array. The Main method initializes an array, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

The program demonstrates the step-by-step execution of the quick sort algorithm on the given array and outputs the sorted array.

Quick sort is a highly efficient sorting algorithm in practice, although its worst-case time complexity is O(n^2). Various optimizations, such as choosing a good pivot or using randomized quick sort, can help mitigate the worst-case scenario and improve its average performance.