+1 vote
153 views

| 153 views

+1 vote

Choosing a median will not always give O(nlogn) T.C.

Example :-

$\rightarrow$ Suppose we have array ${\color{Red} 4}_{0},{\color{Blue} 2}_{1},{\color{Orange} 1}_{2},{\color{Brown} 3}_{3},5_{4}$

$\rightarrow$ where subscript denotes its position in the array.

Partition algo puts elements less than pivot on LHS of pivot and elements greater than equal to pivot on RHS of pivot.

$\rightarrow$ eg:-${\color{Red} 4}_{0}$ represents that $\color{Red} 4$ is at index 0 of the array.

$\rightarrow$ At first we select ${\color{Orange} 1}_{2}$ as pivot so after running partition algo ${\color{Orange} 1}$ comes in $0^{th}$ index of array.

$\rightarrow$ Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Red} 4}_{1},{\color{Blue} 2}_{2},{\color{Brown} 3}_{3},5_{4},$

$\rightarrow$ we select ${\color{Blue} 2}_{2}$ as pivot so after running partition algo ${\color{Blue} 2}$ comes in $1^{st}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Red} 4}_{2},{\color{Brown} 3}_{3},5_{4}$

$\rightarrow$ we select ${\color{Brown} 3}_{3}$ as pivot so after running partition algo ${\color{Brown} 3}$ comes in $2^{nd}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3},5_{4}$

$\rightarrow$ we select ${\color{Red} 4}_{3}$ as pivot so after running partition algo ${\color{Red} 4}$ comes in $3^{rd}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3}(sorted),5_{4}$

$\rightarrow$ we select $5_{4}$ as pivot so after running partition algo $5$ comes in $4^{th}$ index of array.

$\rightarrow$Now the array becomes ${\color{Orange} 1}_{0}(sorted) ,{\color{Blue} 2}_{1}(sorted),{\color{Brown} 3}_{2}(sorted),{\color{Red} 4}_{3}(sorted),5_{4}(sorted)$

$\rightarrow$ So here Partition Algo runs for $n$ times and T.C. of partition Algo is $O(n)$

$\rightarrow$ where $n\rightarrow$ number of elements in the array.

$\therefore$ Total time complexity $= n*O(n) = O(n^{2})$

by Boss (25.1k points)
edited by
0

@Satbir

if we choose median as pivot then recurrence relation will be T(n) = 2T(n/2) + O(n) = O(nlgn) because partition procedure takes O(n) time and median(pivot) divides the array into two equal halves(subproblems) where we again apply the quick sort algo recursively .. So,  in every case where median is pivot element , time complexity will be O(nlgn).. right?

0

@ankitgupta.1729 You are correct but I am considering the special case when pivot is the smallest element.

recurrence relation will be T(n) = T(n-1) + T(1) +O(n).

Implement the example which i gave by yourself for better understanding.

It will create a skewed tree where pivot element comes on one side and unsorted elements come on other branch then the unsorted branch will again split and one branch will be pivot and other branch will have all unsorted elements and the process goes on.

0

@Satbir

@ankitgupta.1729

Bhai, have you guys read on Hoare's partition in that they've mentioned that even when all elements are same even then TC comes out to be Theta (nlogn)

0

Also I have one more doubt related to this - @Satbir

@ankitgupta.1729

Let's say our Partition Algorithm always choose median as pivot element then what will be the Time Complexity of Quicksort when inputs are as follows -

Case a) I/P array is sorted or nearly sorted (default ascending order sorting)

Case b) I/P array is reverse sorted.

Case c) all the elements of input array are same/identical.

Case d) i/p is some arbitrary/random unsorted array.

How about partition algorithms splits? Will they always be balanced like nearly n/2 and n/2 in all the cases?

+1

@iarnav

Hoare's partition has mentioned that even when all elements are same even then TC comes out to be Theta (nlogn) but this case is correct only if we choose median as pivot. If we choose first or last then it will give O(n^2).

case a) I/P is nearly sorted then it will be O(nlogn) because Partition will split the array evenly most of the times.

case b) Array is reverse sorted then i think it will be nlogn because the split will be even.

see like 5,4,3,2,1 will become 2,1,$3$,5,4 then we solve 2,1.

case c) if array has same elements. O(nlogn) if we use median as pivot.

case d) i/p is some arbitrary/random unsorted array. then it will be O(nlogn) since we consider average case here.

+1

@Satbir can you please give me reference for your statement "when all the elements are same then it doesn't matter which element you take as pivot. T.C. will come O(n^2)"? why you are pushing everytime median(pivot)  in initial position of that subarray, median is already in correct position

0

@ankitgupta.1729

I was wrong I unnecessarily swapped my pivot to first position. Please check my answer again i have updated it and tell me if its wrong or correct.

Sorry for my blunder mistake.

+1
"At first we select $1_2$ as pivot so after running partition algo 1 comes in 0th index of array."

"1" is 'middle' element of the array not 'median'... median means middle element of the sorted array.. So, in your example,  median will be 3 because it is the middle element after sorting your array. So,  we should have to take '3' as pivot initially not '1'.
+1
Ok thanks :)
+1

Thank you both of you for your insight and sharing your knowledge. Much love and Thanks! :)

@ankitgupta.1729

@Satbir