DESCRIPTION :
Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one
of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
QUICKSORT(arr[], int low, int high)
1. if(low < high)
2. p = PARTITION(arr,low,high);
3 QUICKSORT(arr,low,p - 1);
4. QUICKSORT(arr,p + 1,high);
PARTITION(arr,low,high)
1. pivot = arr[high];
2. i = (low - 1);
3. for(j = low; j <= high - 1; j++)
4. if(arr[j] < pivot)
5. i = i + 1
6. swap(arr[i],arr[j])
7. swap(arr[i + 1],arr[high])
8. return i + 1
Average Case : θ(n log(n))
Best Case : Ω(n log(n))
Worst Case : O(n^2)
OverAll Space Complexity
=
Auxiliary Space + Space taken by Input
Auxiliary Space is the extra space or temporary space used by an algorithm.
Average Case / Best Case :
Auxiliary Space : O(logn)
Space Taken by Input : O(n)
OverAll Space Complexity : O(n)
Worst Case :
Auxiliary Space : O(n)
Space Taken by Input : O(n)
OverAll Space Complexity : O(n)