mirror of
https://github.com/TheAlgorithms/Python.git
synced 2026-09-28 13:33:11 +08:00
ModusensusandChristian Clauss
1d64d4cda6
* sorts: make quick_sort_3_partition generic over Comparable items * sorts: rebase quick_sort_3_partition generic change onto upstream rewrite --------- Co-authored-by: Christian Clauss <cclauss@me.com>
273 lines
7.4 KiB
Python
273 lines
7.4 KiB
Python
from random import randrange
|
|
from typing import Any, Protocol
|
|
|
|
|
|
class Comparable(Protocol):
|
|
def __lt__(self, other: Any, /) -> bool: ...
|
|
|
|
|
|
def quick_sort_3partition[T: Comparable](
|
|
sorting: list[T], left: int, right: int
|
|
) -> None:
|
|
""" "
|
|
Python implementation of the quicksort algorithm with 3-way partition.
|
|
The idea of 3-way quicksort is based on "Dutch National Flag algorithm".
|
|
|
|
:param sorting: sort list
|
|
:param left: left endpoint of sorting
|
|
:param right: right endpoint of sorting
|
|
:return: None
|
|
|
|
Examples:
|
|
>>> array1 = [5, -1, -1, 5, 5, 24, 0]
|
|
>>> quick_sort_3partition(array1, 0, 6)
|
|
>>> array1
|
|
[-1, -1, 0, 5, 5, 5, 24]
|
|
>>> array2 = [9, 0, 2, 6]
|
|
>>> quick_sort_3partition(array2, 0, 3)
|
|
>>> array2
|
|
[0, 2, 6, 9]
|
|
>>> array3 = []
|
|
>>> quick_sort_3partition(array3, 0, 0)
|
|
>>> array3
|
|
[]
|
|
"""
|
|
if right <= left:
|
|
return
|
|
a = i = left
|
|
b = right
|
|
pivot = sorting[left]
|
|
while i <= b:
|
|
if sorting[i] < pivot:
|
|
sorting[a], sorting[i] = sorting[i], sorting[a]
|
|
a += 1
|
|
i += 1
|
|
elif sorting[i] > pivot:
|
|
sorting[b], sorting[i] = sorting[i], sorting[b]
|
|
b -= 1
|
|
else:
|
|
i += 1
|
|
quick_sort_3partition(sorting, left, a - 1)
|
|
quick_sort_3partition(sorting, b + 1, right)
|
|
|
|
|
|
def quick_sort_lomuto_partition[T: Comparable](
|
|
sorting: list[T], left: int, right: int
|
|
) -> None:
|
|
"""
|
|
A pure Python implementation of the quicksort algorithm(in-place)
|
|
with Lomuto partition scheme:
|
|
https://en.wikipedia.org/wiki/Quicksort#Lomuto_partition_scheme
|
|
|
|
:param sorting: sort list
|
|
:param left: left endpoint of sorting
|
|
:param right: right endpoint of sorting
|
|
:return: None
|
|
|
|
Examples:
|
|
>>> nums1 = [0, 5, 3, 1, 2]
|
|
>>> quick_sort_lomuto_partition(nums1, 0, 4)
|
|
>>> nums1
|
|
[0, 1, 2, 3, 5]
|
|
>>> nums2 = []
|
|
>>> quick_sort_lomuto_partition(nums2, 0, 0)
|
|
>>> nums2
|
|
[]
|
|
>>> nums3 = [-2, 5, 0, -4]
|
|
>>> quick_sort_lomuto_partition(nums3, 0, 3)
|
|
>>> nums3
|
|
[-4, -2, 0, 5]
|
|
"""
|
|
if left < right:
|
|
pivot_index = lomuto_partition(sorting, left, right)
|
|
quick_sort_lomuto_partition(sorting, left, pivot_index - 1)
|
|
quick_sort_lomuto_partition(sorting, pivot_index + 1, right)
|
|
|
|
|
|
def lomuto_partition[T: Comparable](sorting: list[T], left: int, right: int) -> int:
|
|
"""
|
|
Example:
|
|
>>> lomuto_partition([1,5,7,6], 0, 3)
|
|
2
|
|
"""
|
|
pivot = sorting[right]
|
|
store_index = left
|
|
for i in range(left, right):
|
|
if sorting[i] < pivot:
|
|
sorting[store_index], sorting[i] = sorting[i], sorting[store_index]
|
|
store_index += 1
|
|
sorting[right], sorting[store_index] = sorting[store_index], sorting[right]
|
|
return store_index
|
|
|
|
|
|
def hoare_partition_by_value[T: Comparable](
|
|
array: list[T], pivot_value: T, start: int = 0, end: int | None = None
|
|
) -> int:
|
|
"""
|
|
Returns the starting index of the right subarray, which contains the
|
|
elements greater than or equal to `pivot_value`
|
|
|
|
>>> list_unsorted = [7, 3, 5, 4, 1, 8, 6]
|
|
>>> array = list_unsorted.copy()
|
|
>>> hoare_partition_by_value(array, 5)
|
|
3
|
|
>>> array
|
|
[1, 3, 4, 5, 7, 8, 6]
|
|
|
|
Edge cases:
|
|
>>> hoare_partition_by_value(list_unsorted.copy(), 0)
|
|
0
|
|
>>> hoare_partition_by_value(list_unsorted.copy(), 1)
|
|
0
|
|
>>> hoare_partition_by_value(list_unsorted.copy(), 2)
|
|
1
|
|
>>> hoare_partition_by_value(list_unsorted.copy(), 8)
|
|
6
|
|
>>> hoare_partition_by_value(list_unsorted.copy(), 9)
|
|
7
|
|
|
|
"""
|
|
if end is None:
|
|
end = len(array) - 1
|
|
|
|
left = start
|
|
right = end
|
|
|
|
while True:
|
|
"""
|
|
In an intermediate iteration, state could look like this:
|
|
|
|
lllluuuuuuuuuurrrrr
|
|
^ ^
|
|
| |
|
|
left right
|
|
|
|
Where the middle values are unknown (u), since they are not yet traversed.
|
|
`left-1` points to the end of the left subarray.
|
|
`right+1` points to the start of the right subarray.
|
|
"""
|
|
|
|
while array[left] < pivot_value:
|
|
left += 1
|
|
if left > end:
|
|
# Right subarray is empty.
|
|
# Signal it by returning an index out of bounds.
|
|
return end + 1
|
|
while array[right] >= pivot_value:
|
|
right -= 1
|
|
if right < start:
|
|
# Left subarray is empty
|
|
return start
|
|
|
|
if left > right:
|
|
break
|
|
|
|
# Invariants:
|
|
assert all(i < pivot_value for i in array[start:left])
|
|
assert all(i >= pivot_value for i in array[right + 1 : end])
|
|
"""
|
|
llllllruuuuulrrrrrr
|
|
^ ^
|
|
| |
|
|
left right
|
|
"""
|
|
|
|
# Swap
|
|
array[left], array[right] = array[right], array[left]
|
|
|
|
left += 1
|
|
right -= 1
|
|
|
|
return right + 1
|
|
|
|
|
|
def hoare_partition_by_pivot[T: Comparable](
|
|
array: list[T], pivot_index: int, start=0, end: int | None = None
|
|
) -> int:
|
|
"""
|
|
Returns the new pivot index after partitioning
|
|
|
|
>>> array = [7, 3, 5, 4, 1, 8, 6]
|
|
>>> array[3]
|
|
4
|
|
>>> hoare_partition_by_pivot(array, 3)
|
|
2
|
|
>>> array
|
|
[1, 3, 4, 6, 7, 8, 5]
|
|
"""
|
|
if end is None:
|
|
end = len(array) - 1
|
|
|
|
def swap(i1, i2):
|
|
array[i1], array[i2] = array[i2], array[i1]
|
|
|
|
pivot_value = array[pivot_index]
|
|
swap(pivot_index, end)
|
|
greater_or_equal = hoare_partition_by_value(
|
|
array, pivot_value, start=start, end=end - 1
|
|
)
|
|
swap(end, greater_or_equal)
|
|
return greater_or_equal
|
|
|
|
|
|
def quicksort_hoare[T: Comparable](
|
|
array: list[T], start: int = 0, end: int | None = None
|
|
) -> None:
|
|
"""
|
|
Quicksort using the Hoare partition scheme:
|
|
- https://en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
|
|
- The Art of Computer Programming, Volume 3: Sorting and Searching
|
|
|
|
>>> array = [2, 2, 8, 0, 3, 7, 2, 1, 8, 8]
|
|
>>> quicksort_hoare(array)
|
|
>>> array
|
|
[0, 1, 2, 2, 2, 3, 7, 8, 8, 8]
|
|
"""
|
|
if end is None:
|
|
end = len(array) - 1
|
|
|
|
if end + 1 - start <= 1:
|
|
return
|
|
|
|
pivot_index_final = hoare_partition_by_pivot(
|
|
array, randrange(start, end), start, end
|
|
)
|
|
quicksort_hoare(array, start, pivot_index_final - 1)
|
|
quicksort_hoare(array, pivot_index_final + 1, end)
|
|
|
|
|
|
def three_way_radix_quicksort[T: Comparable](sorting: list[T]) -> list[T]:
|
|
"""
|
|
Three-way radix quicksort:
|
|
https://en.wikipedia.org/wiki/Quicksort#Three-way_radix_quicksort
|
|
First divide the list into three parts.
|
|
Then recursively sort the "less than" and "greater than" partitions.
|
|
|
|
>>> three_way_radix_quicksort([])
|
|
[]
|
|
>>> three_way_radix_quicksort([1])
|
|
[1]
|
|
>>> three_way_radix_quicksort([-5, -2, 1, -2, 0, 1])
|
|
[-5, -2, -2, 0, 1, 1]
|
|
>>> three_way_radix_quicksort([1, 2, 5, 1, 2, 0, 0, 5, 2, -1])
|
|
[-1, 0, 0, 1, 1, 2, 2, 2, 5, 5]
|
|
"""
|
|
if len(sorting) <= 1:
|
|
return sorting
|
|
return (
|
|
three_way_radix_quicksort([i for i in sorting if i < sorting[0]])
|
|
+ [i for i in sorting if i == sorting[0]]
|
|
+ three_way_radix_quicksort([i for i in sorting if i > sorting[0]])
|
|
)
|
|
|
|
|
|
if __name__ == "__main__":
|
|
import doctest
|
|
|
|
doctest.testmod(verbose=True)
|
|
|
|
user_input = input("Enter numbers separated by a comma:\n").strip()
|
|
unsorted = [int(item) for item in user_input.split(",")]
|
|
quick_sort_3partition(unsorted, 0, len(unsorted) - 1)
|
|
print(unsorted)
|