The Median of Medians algorithm is a linear time algorithm to solve selection problem or to find median of an unsorted list. In this video, we construct and illustrate form scratch.

------------------
Time Stamps:

00:00 Intro
00:30 - Selection Problem
02:46 - First Idea (Quick Select Algorithm)
04:26 - Prune and Search Technique
05:45 - Approximate Median or Good Pivot
06:45 - Find Median of Medians and Analysis
09:40 - Runtime Analysis
12:16 - Illustration with an example
14:16 - Take Away
15:10 - Problems to Think About
------------------
IdeaBehind Series on Algorithms is a series of 15-20 (we'll count later) animated videos exploring, otherwise mysterious, algorithms in an intuitive perspective. Feedback and suggestions are welcome.
------------------

Bundle of thanks to Reed Mathis for background music.
Animations done in ManimGL with Huge Thanks to Grant Sanderson.

свернуть