Module 14 · The Algorithms You Will Use Weekly: accumulate to nth_element
Under the Hood: Introselect, next_permutation's Four Moves and the Sum That Wraps
ProReading
Kenji's job finds the middle value of 10,000,000 sensor readings. With sort it took 1.3 to 2.5 seconds on Compiler Explorer; with nth_element, about 0.1 seconds. The same night his total of 100,000 readings, each one 100,000, came out as 1410065408.
Checking what this lesson needs for you…
What is inside Under the Hood: Introselect, next_permutation's Four Moves and the Sum That Wraps
- GCC 12's own next_permutation, line by line
- The four moves, one call at a time
- Why a call costs about 3 comparisons on average
- nth_element is introselect
- Measured: introselect against sort
- partial_sort is a heap
- accumulate's loop, and the sum that wraps
- unique and minmax_element in the source
- The performance lab: sort, nth_element and partial_sort