>>> quick_select([2, 4, 5, 7, 899, 54, 32], 5) 54 >>> quick_select([2, 4, 5, 7, 899, 54, 32], 1) 4 >>> quick_select([5, 4, 3, 2], 2) 4 >>> quick_select([3, 5, 7, 10, 2, 12], 3) 7
(items: list, index: int)
| 28 | |
| 29 | |
| 30 | def quick_select(items: list, index: int): |
| 31 | """ |
| 32 | >>> quick_select([2, 4, 5, 7, 899, 54, 32], 5) |
| 33 | 54 |
| 34 | >>> quick_select([2, 4, 5, 7, 899, 54, 32], 1) |
| 35 | 4 |
| 36 | >>> quick_select([5, 4, 3, 2], 2) |
| 37 | 4 |
| 38 | >>> quick_select([3, 5, 7, 10, 2, 12], 3) |
| 39 | 7 |
| 40 | """ |
| 41 | # index = len(items) // 2 when trying to find the median |
| 42 | # (value of index when items is sorted) |
| 43 | |
| 44 | # invalid input |
| 45 | if index >= len(items) or index < 0: |
| 46 | return None |
| 47 | |
| 48 | pivot = items[random.randint(0, len(items) - 1)] |
| 49 | count = 0 |
| 50 | smaller, equal, larger = _partition(items, pivot) |
| 51 | count = len(equal) |
| 52 | m = len(smaller) |
| 53 | |
| 54 | # index is the pivot |
| 55 | if m <= index < m + count: |
| 56 | return pivot |
| 57 | # must be in smaller |
| 58 | elif m > index: |
| 59 | return quick_select(smaller, index) |
| 60 | # must be in larger |
| 61 | else: |
| 62 | return quick_select(larger, index - (m + count)) |
| 63 | |
| 64 | |
| 65 | def median(items: list): |