Three way partition the data into smaller, equal and greater lists, in relationship to the pivot :param data: The data to be sorted (a list) :param pivot: The value to partition the data on :return: Three list: smaller, equal and greater
(data: list, pivot)
| 9 | |
| 10 | |
| 11 | def _partition(data: list, pivot) -> tuple: |
| 12 | """ |
| 13 | Three way partition the data into smaller, equal and greater lists, |
| 14 | in relationship to the pivot |
| 15 | :param data: The data to be sorted (a list) |
| 16 | :param pivot: The value to partition the data on |
| 17 | :return: Three list: smaller, equal and greater |
| 18 | """ |
| 19 | less, equal, greater = [], [], [] |
| 20 | for element in data: |
| 21 | if element < pivot: |
| 22 | less.append(element) |
| 23 | elif element > pivot: |
| 24 | greater.append(element) |
| 25 | else: |
| 26 | equal.append(element) |
| 27 | return less, equal, greater |
| 28 | |
| 29 | |
| 30 | def quick_select(items: list, index: int): |