(list, k)
| 23 | return less, equal, greater |
| 24 | |
| 25 | def quickSelect(list, k): |
| 26 | #k = len(list) // 2 when trying to find the median (index that value would be when list is sorted) |
| 27 | smaller = [] |
| 28 | larger = [] |
| 29 | pivot = random.randint(0, len(list) - 1) |
| 30 | pivot = list[pivot] |
| 31 | count = 0 |
| 32 | smaller, equal, larger =_partition(list, pivot) |
| 33 | count = len(equal) |
| 34 | m = len(smaller) |
| 35 | |
| 36 | #k is the pivot |
| 37 | if m <= k < m + count: |
| 38 | return pivot |
| 39 | # must be in smaller |
| 40 | elif m > k: |
| 41 | return quickSelect(smaller, k) |
| 42 | #must be in larger |
| 43 | else: |
| 44 | return quickSelect(larger, k - (m + count)) |
nothing calls this directly
no test coverage detected