sorts.quick_sort_3_partition
============================

.. py:module:: sorts.quick_sort_3_partition


Attributes
----------

.. autoapisummary::

   sorts.quick_sort_3_partition.user_input


Functions
---------

.. autoapisummary::

   sorts.quick_sort_3_partition.lomuto_partition
   sorts.quick_sort_3_partition.quick_sort_3partition
   sorts.quick_sort_3_partition.quick_sort_lomuto_partition
   sorts.quick_sort_3_partition.three_way_radix_quicksort


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

.. py:function:: lomuto_partition(sorting: list, left: int, right: int) -> int

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


.. py:function:: quick_sort_3partition(sorting: list, left: int, right: int) -> None

   "
   Python implementation of quick sort algorithm with 3-way partition.
   The idea of 3-way quick sort 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
   []


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

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


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


.. py:data:: user_input