882 views

1 Answer

1 votes
1 votes

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})$

edited by

Related questions

0 votes
0 votes
2 answers
1
iarnav asked Apr 25, 2019
967 views
I did Google and found out that Quicksort is better then Mergesort, but my question is which is faster among both?
3 votes
3 votes
2 answers
2
dhruba asked Jun 5, 2023
985 views
In QuickSort algorithm, which of the following statements is NOT true regarding the partition process?a) Partition always divides the array into two non-empty subsets.b) ...
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4