Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.[contradictory]
Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. In an efficient implementation it is not a stable sort, meaning that the relative order of equal sort items is not preserved. Quicksort can operate in-place on an array, requiring small additional amounts of memory to perform the sorting. It is very similar to selection sort, except that it does not always choose the worst-case partition.
using System;
namespace QuickSort
{
class Program
{
private static void PrintArray(int[] arr)
{
for(int i = 0; i < arr.Length; i++)
{
Console.Write(arr[i] + " ");
}
Console.WriteLine();
}
private static int Partition(int[] arr, int start, int end)
{
int pivot = arr[end];
int i = start-1;
for(int j = start; j < end; j++)
{
if (arr[j] < pivot)
{
i++;
int tempVar = arr[i];
arr[i] = arr[j];
arr[j] = tempVar;
}
}
int temp = arr[i + 1];
arr[i + 1] = pivot;
arr[end] = temp;
return (i + 1);
}
private static void QuickSortUtil(int[] arr, int start, int end)
{
if(end > start)
{
int pivot = Partition(arr, start, end);
QuickSortUtil(arr, start, pivot - 1);
QuickSortUtil(arr, pivot + 1, end);
}
}
private static void QuickSort(int[] arr)
{
QuickSortUtil(arr, 0, arr.Length-1);
}
static void Main(string[] args)
{
int[] arr = new int[] { 4, 7, 2, 8, 1, 9, 3, 5, 6 };
PrintArray(arr);
QuickSort(arr);
PrintArray(arr);
}
}
}
Output :
4 7 2 8 1 9 3 5 6
1 2 3 4 5 6 7 8 9
Press any key to continue . . .The Time complexity of above Solution is O(nlogn). it is using Divide and Conquer approach.
