Median of medians is an approximate median selection algorithm used to supply a good pivot for an exact selection algorithm, such as quickselect. It finds an approximate median in linear time and can be used in quicksort to optimize the worst-case complexity to O(nlog n). It was published in Blum et al. (1973) and is sometimes referred to as BFPRT.
Stanford University
Winter 2023
This course provides an in-depth exploration of algorithm analysis and design. It covers various sorting, searching, and selection algorithms, data structures, and fundamental graph algorithms. It emphasizes the understanding of worst and average case analysis, recurrences, and asymptotics.
No concepts data
+ 30 more concepts