To avoid this, you can pick random pivot element too. If someone knows that you pick the last index as pivot all the time, they can intentionally provide you with array which will result in worst-case running time for quick sort. Worst Case Time Complexity : O(n 2)īest Case Time Complexity : O(n*log n)Īverage Time Complexity : O(n*log n)Īs we know now, that if subarrays partitioning produced after partitioning are unbalanced, quick sort will take more time to finish. Where as if partitioning leads to almost equal subarrays, then the running time is the best, with time complexity as O(n*log n). Void quickSort(int a, int beg, int end)įor an array, in which partitioning leads to unbalanced subarrays, to an extent where on the left side there are no elements, with all the elements greater than the pivot, hence on the right side.Īnd if keep on getting unbalanced subarrays, then the running time is the worst case, which is O(n 2) In this tutorial, we will take the rightmost element or the last element as pivot.įor example: In the array Pivot element can be any element from the array, it can be the first element, the last element or any random element. Elements greater than the pivot element.This algorithm divides the list into three main parts: It is also called partition-exchange sort. In case of quick sort, the combine step does absolutely nothing. But in quick sort all the heavy lifting(major work) is done while dividing the array into subarrays, while in case of merge sort, all the real work happens during merging the subarrays. Quick Sort is one of the different Sorting Technique which is based on the concept of Divide and Conquer, just like merge sort.

Exchange sorty