Median of medians Algorithm - [Linear Time Complexity O(n)] #PART-1

Median of medians can be used as a pivot strategy in quicksort, yielding an optimal algorithm.

10, 1, 67, 20, 56, 8 ,43, 90, 54, 34, 0

for this array the median will be 34.

0 1 8 10 20 34 43 54 56 67 90

Now the naive solution for this problem would be something like, first you sort the array, and then get the middle index element. But that approach does more work than required, as you just need to find the median, there's no need to know the sorted position of each element in the array.
and the worst time complexity for this solution is O(nlogn)

There's another solution for this problem that has complexity O(n), which is based on quick sort algorithm. so what we do,

we choose a pivot element,
then rearrange numbers exactly like we used to do in quick sort
then we return the pivot index.
Now we check if the index is the middle index.
if it is, we have found the median
if pivot index is less than median index, we recursively search for the median in right subarray. lse if pivot index is greater than median index, we recursively search in the left subarray.

[benzeltser]

I need to transfer the University money to you instead.

[regilkoshy]

Finally, I saw someone teaching with example. I was tired of people explaining with (i, j), x, y etc. I rather see actual example and learn instead of talking about all those symbols and letters for constants etc.

[andreicozma]

This video is full of errors. You may try to decipher them yourself, but otherwise you'll end up more confused. Save your time and look for another video.

[viharisunkara]

I think, in the pivot approach, it is N + N-1 + N-2 +.. = O(N^2)

[debarchanbasu]

Good effort though. But not a good explanation. Riddled with errors.

[friendlylaser]

Still don't get why this works. Does not click for me for some reason.

[lauramarianella]

Thank you!! It's more clear than my professor's lesson 🤭

[khalidfrom]

your accent is super good, a lot of thanks.

[abhishekchaudhary]

Nicely explained. Please keep up the good work.

[jialanwang]

Thanks for working out an example! I totally needed it.

[aravindkumaresan]

Is there any real proof that this algorithm works better than normal quick sort based pivot one. Because dividing the whole array into various sub array of fixed size and sorting them to find median is too expensive, isn't ?

[subratakumarbiswas]

why u r searching for 6th element at first? the array is of size 11 so the median will be 5th element so index 4th... you confused me even more.

[hanmingwong]

Hey with regards to the last array with length 2, how did u determine that in [13, 34], 34 is a pivot/median?

[abhishekmazumdar]

You didn't show the fun part where average case become linear.

[mironabdullah]

It Is just shit. Though I appreciate your hard work. from Denmark

[slowmotion]

Very Poor explanation, the video doesn't quite relate to what is being said.