using System;

using System.Collections.Generic;

using System.Linq;

using System.Text.RegularExpressions;

namespace CSharpAlgorithms

{

public class Program

{

public static void Main(string[] args)

{

int[] arr = { 1, 6, 2, 5, 4, 3 };

QuickSort(arr, 0, 5);

arr.ToList().ForEach(i => Console.WriteLine(i.ToString()));

}

public static void QuickSort(int[] array, int left, int right)

{

if(left > right || left <0 || right <0) return;

int index = Partition(array, left, right);

if (index != -1)

{

QuickSort(array, left, index - 1);

QuickSort(array, index + 1, right);

}

}

private static int Partition(int[] array, int left, int right)

{

if(left > right) return -1;

int end = left;

int pivot = array[right]; // choose last one to pivot, easy to code

for(int i= left; i< right; i++)

{

if (array[i] < pivot)

{

Swap(array, i, end);

end++;

}

}

Swap(array, end, right);

return end;

}

private static void Swap(int[] array, int left, int right)

{

int tmp = array[left];

array[left] = array[right];

array[right] = tmp;

}

}

}