CODEWITHSUNDEEP
algorithmsortingcomplexity-theoryquicksort
roggy
roggy

Reputation: 64

quick sort complexity in worst case with pivot middle element

As quick sort complexity in worst case is O(n^2)

In an increasing order case when pivot selected first or last element it gives correct worst case complexity of O(n^2) as always one child of tree is empty

but when pivot selected middle ,i am getting confused? it divides the tree into half that makes its complexity O(n.logn)

let say 10 20 30 40 50 60 70 pivot=40

(10 20 30 ) 40 (50 60 70)

left side pivot 20, right side pivot 60

(10) 20 (30)

(50) 60 (70)

is it correct????

Upvotes: 3

Views: 11693

Answers (4)

Ashish Padhy
Ashish Padhy

Reputation: 71

Yes, If the array is already sorted and we are choosing middle element as pivot, it gives O(nlogn) time complexity.

That's why it's preferred as a pivot.

Upvotes: 0

Jeff Tsui
Jeff Tsui

Reputation: 1276

When a pivot is selected, the list is partitioned so that the elements to the left of the pivot are smaller than the pivot and the elements to the right are larger. At this point, the sorting problem is NOT divided in half as you describe.

After selecting a pivot, you would need to sort the left and right partitions. This would involve selecting a new pivot for each and partitioning. Quick sort proceeds recursively until there is only a single right and left partition.

I would suggest reviewing the quick sort algorithm and manually going through a couple examples from start to end.

The following animation helps if you are a visual learner: http://www.csanimated.com/animation.php?t=Quicksort

Upvotes: 0

Gene
Gene

Reputation: 46960

The point is that you're selecting the pivot from an unsorted array. So the value is random. If e.g. you happen to pick the lowest value every time, the partition will have nothing on the left side. This means each recursive call on the right will handle one less element than the previous one. Roughly speaking, the total work done by these calls will be O(sum(i) for i = n downto 1) = O(n^2).

Upvotes: 0

wvdz
wvdz

Reputation: 16641

In your example, you assume the list to be sorted is already sorted.

In this case, quick sort will indeed perform O(n^2) when you always pick the first or last item as a pivot.

If you pick the middle item, it is certainly possible that it will have bad performance. For instance:

1 2 3 4 (5) 1 2 3 4

Now, since there are no items higher than 5, this is a bad pivot, even though it is a middle element.

Because sorting sorted lists is a common scenario, using the first or last item as the pivot is considered a bad practice. In general, the middle item is less likely to be a bad pivot.

Upvotes: 2

Related Questions