sorts.quick_sort_3_partition

Attributes

user_input

Classes

Comparable

Base class for protocol classes.

Functions

hoare_partition_by_pivot(→ int)

Returns the new pivot index after partitioning

hoare_partition_by_value(→ int)

Returns the starting index of the right subarray, which contains the

lomuto_partition(→ int)

Example:

quick_sort_3partition(→ None)

quick_sort_lomuto_partition(→ None)

A pure Python implementation of the quicksort algorithm(in-place)

quicksort_hoare(→ None)

Quicksort using the Hoare partition scheme:

three_way_radix_quicksort(→ list[T])

Three-way radix quicksort:

Module Contents

class sorts.quick_sort_3_partition.Comparable

Bases: Protocol

Base class for protocol classes.

Protocol classes are defined as:

class Proto(Protocol):
    def meth(self) -> int:
        ...

Such classes are primarily used with static type checkers that recognize structural subtyping (static duck-typing).

For example:

class C:
    def meth(self) -> int:
        return 0

def func(x: Proto) -> int:
    return x.meth()

func(C())  # Passes static type check

See PEP 544 for details. Protocol classes decorated with @typing.runtime_checkable act as simple-minded runtime protocols that check only the presence of given attributes, ignoring their type signatures. Protocol classes can be generic, they are defined as:

class GenProto[T](Protocol):
    def meth(self) -> T:
        ...
__lt__(other: Any, /) → bool
sorts.quick_sort_3_partition.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]
sorts.quick_sort_3_partition.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

sorts.quick_sort_3_partition.lomuto_partition[T: Comparable](sorting: list[T], left: int, right: int) → int

Example: >>> lomuto_partition([1,5,7,6], 0, 3) 2

sorts.quick_sort_3_partition.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”.

Parameters:

  • sorting – sort list

  • left – left endpoint of sorting

  • right – right endpoint of sorting

Returns:

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 []

sorts.quick_sort_3_partition.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

Parameters:

  • sorting – sort list

  • left – left endpoint of sorting

  • right – right endpoint of sorting

Returns:

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]

sorts.quick_sort_3_partition.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]
sorts.quick_sort_3_partition.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]
sorts.quick_sort_3_partition.user_input