divide_and_conquer.minimum_element_of_array

Return the minimum element of an array using the divide-and-conquer algorithm for selection sort. Like quicksort, it partitions the input array recursively. But unlike quicksort, which recursively processes both sides of the partition, this algorithm works on only one side of the partition. The expected running time of this selection sort algorithm is 0(n), assuming that the elements are distinct. It returns the ith smallest element of the array A[p: r], where 1 ≤ i ≤ r-p+1. (From Introduction to Algorithms, Fourth Edition, Cormen, 2022: Chapter 9.2)

Functions

partition(→ int)	Partition the array.
randomized_partition(→ int)	Randomized partition of the array.
selection_sort(→ list | None)	Returns a list of sorted array elements using selection sort.

Module Contents

divide_and_conquer.minimum_element_of_array.partition(array: list, starting_index: int, ending_index: int) → int

Partition the array. Args:

array: list of elements starting_index: starting index of the array ending_index: ending index of the array

Returns:

index of the pivot

>>> arr = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> partition(arr, 0, len(arr) - 1)
0

divide_and_conquer.minimum_element_of_array.randomized_partition(array: list, starting_index: int, ending_index: int) → int

Randomized partition of the array. Args:

array: list of elements starting_index: starting index of the array ending_index: ending index of the array

Returns:

call to partition function

>>> arr = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> arr1 = randomized_partition(arr, 0, len(arr) - 1)
>>> arr == arr1
False

divide_and_conquer.minimum_element_of_array.selection_sort(array: list, starting_index: int, ending_index: int, smallest_element: int) → list | None

Returns a list of sorted array elements using selection sort. Using selection to find a minimum is O(n) overkill vs. a linear scan — the value here is the DAC/partition demonstration.

Args:

array: list of elements starting_index: starting index of the array ending_index: ending index of the array smallest_element: the ith smallest element of

the array A[p: r], where 1 ≤ i ≤ r-p+1

Returns:

sorted array

>>> from random import shuffle
>>> arr = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> shuffle(arr)
>>> selection_sort(arr, 0, len(arr) - 1, 1)
-200

>>> shuffle(arr)
>>> selection_sort(arr, 0, len(arr) - 1, 1)
-200

>>> arr = [-200]
>>> selection_sort(arr, 0, len(arr) - 1, 1)
-200

>>> arr = [-2]
>>> selection_sort(arr, 0, len(arr) - 1, 1)
-2

>>> arr = []
>>> selection_sort(arr, 0, len(arr) - 1, 1)
[]