# Quick Sort

QuickSort is based on divide-and-conquer approach. QuickSort is inplace sorting algorithm.A sorting algorithm is said to be in-place if it requires very little additional space besides the initial array holding the elements that are to be sorted.

The key to the Algorithm is the Partition Procedure, which rearranges the subarray a[p..r] in place. Partition selects an element x as a pivot element around which to partition the subaaray a[p..r].

```#include<iostream>
using namespace std;

void swap(int *a,int *b)
{
int temp = *a;
*a=*b;
*b = temp;
}
int partition (int A[], int p, int r)
{
int x = A[r];
int i = p - 1;

for (int j = p; j <= r- 1; j++)
{
if (A[j] <= x)
{
i++;
swap (&A[i], &A[j]);
}
}
swap (&A[i + 1], &A[r]);
return (i + 1);
}

void quickSort(int A[], int p, int r)
{
if (p < r)
{
int q = partition(A, p,r);
quickSort(A, p, q - 1);
quickSort(A, q + 1, r);
}
}
int main()
{
int a[] = {2,6,5,1,3,4};
int n = sizeof(a)/sizeof(a[0]);
quickSort(a,0,n-1);
for(int i=0;i<n;i++)
cout<<a[i]<<" ";
return 0;
}
```

Time Complexity : Average case O(nlogn) When the array is balanced partitoned.Worst case O(n^2), worst-case behavior for quicksort occurs when the partition method produces one subproblem with n-1 elements and one with 0 elements.