divide_and_conquer.minimum_element_of_array
===========================================

.. py:module:: divide_and_conquer.minimum_element_of_array

.. autoapi-nested-parse::

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

.. autoapisummary::

   divide_and_conquer.minimum_element_of_array.partition
   divide_and_conquer.minimum_element_of_array.randomized_partition
   divide_and_conquer.minimum_element_of_array.selection_sort


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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)
   []