Tukey's ninther def tukeys_ninthers(items): Back in the day when computers were far slower and had a lot less RAM for our programs to burrow into, special techniques were necessary to achieve many things that are trivial today with a couple of lines of code. In this spirit, "Tukey's ninther" is an approximation algorithm from the seventies to quickly find some value that should be “reasonably close” to the median element of the given unsorted list. For the purposes of this problem, the median element of the list is defined to be the element that would end up in the middle position if that list were sorted. This makes the median unambiguous, regardless of the elements and their multiplicities. This function is not tasked to find the true median, which would be a trivial one liner by sorting items, but find and return the same element that Tukey's ninther algorithm would return for those items. Tukey's algorithm splits the list into triplets of three elements, and finds the median of each triplet. These medians-of-three are collected into a new list and this same operation is repeated until only one element remains. For simplicity, your function can assume that the length of items is always some power of three. In the following table, each row contains the result produced by applying a single round of Tukey's algorithm to the list immediately below.
Tukey's ninther
def tukeys_ninthers(items):
Back in the day when computers were far slower and had a lot less RAM for our programs to burrow into, special techniques were necessary to achieve many things that are trivial today with a couple of lines of code. In this spirit, "Tukey's ninther" is an approximation
Tukey's algorithm splits the list into triplets of three elements, and finds the median of each triplet. These medians-of-three are collected into a new list and this same operation is repeated until only one element remains. For simplicity, your function can assume that the length of items is always some power of three. In the following table, each row contains the result produced by applying a single round of Tukey's algorithm to the list immediately below.
| items | Expected result |
| [15] | 15 |
| [42, 7, 15] | 15 |
| [99, 42, 17, 7, 1, 9, 12, 77, 15] | 15 |
| [55, 99, 131, 42, 88, 11, 17, 16, 104, 2, 8, 7, 0, 1, 69, 8, 93, 9, 12, 11, 16, 1, 77, 90, 15, 4, 123] | 15 |
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 3 images
