Performs Dual-Pivot QuickSort on the input array. Dual-Pivot QuickSort is an optimized version of QuickSort that uses two pivot elements to partition the array into three segments in each recursive call. This improves performance by reducing the number of recursive calls, makin
(arr, low, high)
| 1 | def dual_pivot_quicksort(arr, low, high): |
| 2 | """ |
| 3 | Performs Dual-Pivot QuickSort on the input array. |
| 4 | |
| 5 | Dual-Pivot QuickSort is an optimized version of QuickSort that uses |
| 6 | two pivot elements to partition the array into three segments in each |
| 7 | recursive call. This improves performance by reducing the number of |
| 8 | recursive calls, making it faster on average than the single-pivot |
| 9 | QuickSort. |
| 10 | |
| 11 | Parameters: |
| 12 | arr (list): The list to be sorted. |
| 13 | low (int): The starting index of the segment to sort. |
| 14 | high (int): The ending index of the segment to sort. |
| 15 | |
| 16 | Returns: |
| 17 | None: Sorts the array in place. |
| 18 | """ |
| 19 | if low < high: |
| 20 | # Partition the array and get the two pivot indices |
| 21 | lp, rp = partition(arr, low, high) |
| 22 | # Recursively sort elements less than pivot1 |
| 23 | dual_pivot_quicksort(arr, low, lp - 1) |
| 24 | # Recursively sort elements between pivot1 and pivot2 |
| 25 | dual_pivot_quicksort(arr, lp + 1, rp - 1) |
| 26 | # Recursively sort elements greater than pivot2 |
| 27 | dual_pivot_quicksort(arr, rp + 1, high) |
| 28 | |
| 29 | |
| 30 | def partition(arr, low, high): |
no test coverage detected