C# program to write recursive Quicksort algorithm

Here's a C# program that implements the recursive Quicksort algorithm:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 9, 7, 5, 11, 12, 2, 14, 3, 10, 6 };
        
        Console.WriteLine("Original array:");
        DisplayArray(arr);

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

        Console.WriteLine("\nSorted array:");
        DisplayArray(arr);
    }

    static void Quicksort(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 left and right subarrays
            Quicksort(arr, low, pivotIndex - 1);
            Quicksort(arr, pivotIndex + 1, high);
        }
    }

    static int Partition(int[] arr, int low, int high)
    {
        // Choose the rightmost element as the pivot
        int pivot = arr[high];
        int i = low - 1;

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

        // Swap arr[i+1] and the pivot
        Swap(arr, i + 1, high);

        return i + 1; // Return the pivot index
    }

    static void Swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static void DisplayArray(int[] arr)
    {
        foreach (int element in arr)
        {
            Console.Write(element + " ");
        }
        Console.WriteLine();
    }
}

In this program, we have the Quicksort method that performs the recursive Quicksort algorithm. It takes an array (arr), the low index of the current partition (low), and the high index of the current partition (high) as parameters.

The base case of the recursion is when the low index is less than the high index. In this case, we perform the partitioning step to determine the pivot index, and then recursively call Quicksort on the left and right subarrays.

The Partition method is responsible for the partitioning step. It takes the array, low index, and high index as parameters. The rightmost element (arr[high]) is chosen as the pivot. The method uses the two-pointer approach to partition the array into two sections: elements less than or equal to the pivot on the left side, and elements greater than the pivot on the right side.

The Swap method is a helper method that swaps two elements in the array.

The Main method initializes an array arr, displays the original array, calls the Quicksort method to sort the array, and then displays the sorted array.

Original array:
9 7 5 11 12 2 14 3 10 6

Sorted array:
2 3 5 6 7 9 10 11 12 14

The original array [9, 7, 5, 11, 12, 2, 14, 3, 10, 6] is sorted using the recursive Quicksort algorithm, resulting in the sorted array [2, 3, 5, 6, 7, 9, 10, 11, 12, 14].