Quick Sort

Quick Sort is based on Divide and Conquer strategy. It is also known as Partition Exchange method. Steps of Quick Sort based on Divide and Conquer are as follows: a. Divide : This is initiated by partitioning the given array. For Partition process we choose a Pivot value. This value may be first,last or middle value out of the list. Rearrange the elements in array[low..high] so that all elements in array[low..high] that are less than or equal to the Pivot are to its left(not necessarily in sorted order) and all elements that are greater than the Pivot are to its right (not necessarily in sorted order). This process places the Pivot value at its sorted position. Let p be the pivot index at which pivot value is placed. Once the pivot index is found, we divide the list in to two half a[low,p-1] and a[p+1,high] and Quick Sort is applied on these halves. b. Conquer : By recursively sorting the sub arrays array[low..p-1] (all elements to the left of the Pivot, which must be less than or equal to the pivot) and array[p+1..high] (all elements to the right of the pivot, which must be greater than the pivot). c. Combine : We need not to combine anything in Quick Sort. Once the conquer step recursively returns a pivot index for selected Pivot Value of the sub array, it actually is its sorted position and recursive call of left and right sub array will result sorted array. Complexity : Best Case O(nlogn) Worst Case O(n^2)