sorts.quick_sort_3_partition

Attributes

user_input

Functions

lomuto_partition(→ int)	Example:
quick_sort_3partition(→ None)
quick_sort_lomuto_partition(→ None)	A pure Python implementation of quick sort algorithm(in-place)
three_way_radix_quicksort(→ list)	Three-way radix quicksort:

Module Contents

sorts.quick_sort_3_partition.lomuto_partition(sorting: list, left: int, right: int) → int

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

sorts.quick_sort_3_partition.quick_sort_3partition(sorting: list, left: int, right: int) → None

sorts.quick_sort_3_partition.quick_sort_lomuto_partition(sorting: list, left: int, right: int) → None

A pure Python implementation of quick sort 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.three_way_radix_quicksort(sorting: list) → list

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