One common application of Quickselect is finding the median, which is the middle element (or average of the two middle elements) in a sorted dataset. It works efficiently on unsorted lists by partially sorting the data without fully sorting the entire list. >>> median([3, 2, 2,
(items: list)
| 63 | |
| 64 | |
| 65 | def median(items: list): |
| 66 | """ |
| 67 | One common application of Quickselect is finding the median, which is |
| 68 | the middle element (or average of the two middle elements) in a sorted dataset. |
| 69 | It works efficiently on unsorted lists by partially sorting the data without |
| 70 | fully sorting the entire list. |
| 71 | |
| 72 | >>> median([3, 2, 2, 9, 9]) |
| 73 | 3 |
| 74 | |
| 75 | >>> median([2, 2, 9, 9, 9, 3]) |
| 76 | 6.0 |
| 77 | """ |
| 78 | mid, rem = divmod(len(items), 2) |
| 79 | if rem != 0: |
| 80 | return quick_select(items=items, index=mid) |
| 81 | else: |
| 82 | low_mid = quick_select(items=items, index=mid - 1) |
| 83 | high_mid = quick_select(items=items, index=mid) |
| 84 | return (low_mid + high_mid) / 2 |
nothing calls this directly
no test coverage detected