>>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] >>> partition(array, 0, len(array), 12) 8 >>> array = [21, 15, 11, 45, -2, -11, 46] >>> partition(array, 0, len(array), 15) 3 >>> array = ['a', 'z', 'd', 'p', 'v', 'l', 'o', 'o'] >>> partition(arra
(array: list, low: int, high: int, pivot: int)
| 106 | |
| 107 | |
| 108 | def partition(array: list, low: int, high: int, pivot: int) -> int: |
| 109 | """ |
| 110 | >>> array = [4, 2, 6, 8, 1, 7, 8, 22, 14, 56, 27, 79, 23, 45, 14, 12] |
| 111 | >>> partition(array, 0, len(array), 12) |
| 112 | 8 |
| 113 | >>> array = [21, 15, 11, 45, -2, -11, 46] |
| 114 | >>> partition(array, 0, len(array), 15) |
| 115 | 3 |
| 116 | >>> array = ['a', 'z', 'd', 'p', 'v', 'l', 'o', 'o'] |
| 117 | >>> partition(array, 0, len(array), 'p') |
| 118 | 5 |
| 119 | >>> array = [6.2, -45.54, 8465.20, 758.56, -457.0, 0, 1, 2.879, 1.7, 11.7] |
| 120 | >>> partition(array, 0, len(array), 2.879) |
| 121 | 6 |
| 122 | """ |
| 123 | i = low |
| 124 | j = high |
| 125 | while True: |
| 126 | while array[i] < pivot: |
| 127 | i += 1 |
| 128 | j -= 1 |
| 129 | while pivot < array[j]: |
| 130 | j -= 1 |
| 131 | if i >= j: |
| 132 | return i |
| 133 | array[i], array[j] = array[j], array[i] |
| 134 | i += 1 |
| 135 | |
| 136 | |
| 137 | def sort(array: list) -> list: |