/* Quicksort:-

Quicksort is a divide and conquer algorithm. 

Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. 

Quicksort can then recursively sort the sub-arrays.

​

The steps are:

​

Pick an element, called a pivot, from the array.

Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, 

while all elements with values greater than the pivot come after it (equal values can go either way). 

After this partitioning, the pivot is in its final position. This is called the partition operation.

Recursively apply the above steps to the sub-array of elements with smaller values and separately to the 

sub-array of elements with greater values.

​

Hoare partition scheme:-

The original partition scheme described by C.A.R. Hoare uses two indices that start at the ends of the array being partitioned, 

then move toward each other, until they detect an inversion: a pair of elements, one greater than or equal to the pivot, one lesser 

or equal, that are in the wrong order relative to each other. The inverted elements are then swapped.[18] When the indices meet, 

the algorithm stops and returns the final index. There are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]. 

​

Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions 

even when all values are equal.[10][self-published source?] 

​

Like Lomuto's partition scheme, Hoare partitioning also causes Quicksort to degrade to O(n2) when the input array is already sorted; 

it also doesn't produce a stable sort. Note that in this scheme, the pivot's final location is not necessarily at the index that was returned, 

and the next two segments that the main algorithm recurs on are (lo..p) and (p+1..hi) as opposed to (lo..p-1) and (p+1..hi) as in Lomuto's scheme.

However, the partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite 

recursion. In pseudocode,[16]

​

Average-case analysis:-

To sort an array of n distinct elements, quicksort takes O(n log n) time in expectation, averaged over all n! permutations of n elements with equal 

probability. We list here three common proofs to this claim providing different insights into quicksort's workings.

​

algorithm quicksort(A, lo, hi) is

    if lo < hi then

        p := partition(A, lo, hi)

        quicksort(A, lo, p)

        quicksort(A, p + 1, hi)

​

algorithm partition(A, lo, hi) is

    pivot := A[(lo + hi) / 2]

    i := lo - 1

    j := hi + 1

    loop forever

        do

            i := i + 1

        while A[i] < pivot

​

        do

            j := j - 1

        while A[j] > pivot

​

        if i >= j then

            return j

​

        swap A[i] with A[j]

The entire array is sorted by quicksort(A, 0, length(A)-1).

​

*/

using System;

public class Program

{

    private static int partition(int[] arr, int low, int high)

    {

        int pivot = arr[(low + high) / 2];

        int left = low - 1;

        int right = high + 1;

        while(true)

        {

            do

            {

                left++;

            } while (arr[left] < pivot);

            do

            {

                right--;

            } while (arr[right] > pivot);

            if (left >= right) return right;

            //Swap left and right values.

            int temp = arr[left];

            arr[left] = arr[right];

            arr[right] = temp;      

        }   

    }

    private static void quickSort(int[] arr, int low, int high)

    {

        if (low < high)

        {

            int pivot = partition(arr, low, high);

            quickSort(arr, low, pivot);

            quickSort(arr, pivot+1, high);          

        }

    }

    private static void printArray(int[] arr, int size)

    {

        for(int i=0; i < size ; i++)

        {

           Console.Write(arr[i] + " "); 

        }

        Console.WriteLine();

    }

    public static void Main()

    {

        int[] arr = {10, 7, 8, 9, 1, 5};

        int n = arr.Length;

        quickSort(arr, 0, n-1);

        Console.WriteLine("Quick Sorted Array...");

        printArray(arr, n);

    }

}