Quick Sort Algorithm (Python)

Question

QuickSort is a Divide and Conquer algorithm, which picks an element as "pivot" and partitions a given list around the pivot. There are many different versions of Quick Sort, as to how to pick a pivot in different ways:

• Always pick first element as pivot (implemented below)
• Always pick last element as pivot
• Pick a random element as pivot
• Pick median as pivot

---

Just for practicing, I've implemented the quick sort algorithm, and if you'd like to review it and provide any change/improvement recommendations, please do so, and I appreciate that.

Code

import random
from typing import TypeVar, List
from scipy import stats

T = TypeVar('T')


def quick_sort(input_list: List[T]) -> List[T]:
    """"
    Returns an ascendingly sorted list;
    Input variable is an integer or float array;
    Theoretical Complexity: O(N*Log N) Time and O(N) Memory
    """

    sort(input_list, 0, len(input_list) - 1)
    return input_list


def sort(input_list: List[T], start_index: int, end_index: int) -> None:
    """Recursively sorts the two pivot-divided sublists;"""
    if start_index >= end_index:
        return
    pivot_index = partition(input_list, start_index, end_index)
    sort(input_list, start_index, pivot_index - 1)
    sort(input_list, pivot_index + 1, end_index)


def partition(input_list: List[T], start_index: int, end_index: int) -> int:
    """
    Returns the end index; Partitions a list into two sublists;
    """
    pivot = input_list[start_index]

    i, j = start_index + 1, end_index

    while i <= j:
        while input_list[i] < pivot and i < end_index:
            i += 1
        while input_list[j] > pivot:
            j -= 1

        if i < j:
            temp = input_list[i]
            input_list[i] = input_list[j]
            input_list[j] = temp
            i += 1
            j -= 1
        else:
            break

    input_list[start_index] = input_list[j]
    input_list[j] = pivot

    return j


if __name__ == "__main__":

    # Creates a dash line string and a new line for in between the tests.
    delimiter = "-" * 70 + "\n"

    # Generates a random integer list.
    test_list_integer = random.sample(range(-100, 100), 15) * 3
    print(f"""The unsorted integer array is:
        {test_list_integer}""")
    print(delimiter)

    # Generates a random float list.
    test_list_float = stats.uniform(0, 100).rvs(45)
    print(f"""The unsorted float array is:
        {test_list_float}""")
    print(delimiter)

    # Sample float/integer test list for input.
    integer_float_input = list(test_list_integer + test_list_float)

    # Sample float/integer test list for output.
    integer_float_output = sorted(integer_float_input)

    sorting_algorithms = [
        ("Quick Sort", quick_sort)
    ]

    # Testing
    for description, func in sorting_algorithms:
        if (func(integer_float_input.copy()) == integer_float_output):
            print(f"{description} Test was Successful.")
        else:
            print(f"{description} Test was not Successful.")
        print(f"""{description} (Integer):
            {func(test_list_integer.copy())}""")
        print(f"""{description} (Float):
            {func(test_list_float.copy())}""")
        print(delimiter)

Reference

• Quick Sort - Geeks for Geeks
• Quick Sort - Wiki

Answer 1

I'm all for providing docstrings.
I doubt the docstrings presented are helpful as can be for someone not familiar with the quicksort algorithm:

• Returns an ascendingly sorted list;
  is this a new one or the one provided as input?
  (A method docstring should start with a phrase ending in a period [prescribing the] method's effect as a command ("Do this", "Return that"), not as a description)

• Input variable is an integer or float array;
  doesn't it work for strings?
  the python tutorial names lists and tuples as standard sequence data types - what is an array?
  (The type hint does give a hint as to the intended meaning - I do not have a helpful intuition about python type hinting in general and "interaction" with docstrings in particular.)

• Theoretical Complexity: O(N×Log N) Time and O(N) Memory
  Without further qualification of the bounds claimed, I expect them to be worst case bounds.

• Recursively sorts the two pivot-divided sublists;
  looking at the method interface, only, I don't see two sublists
  (which happens to be the first thing I hope for in a method docstring - The docstring for a function or method should summarize its behavior and document its arguments, … does not stress this.)

There are several things not quite pythonic in the code presented

• a swap of a and b is typically denoted using implied lists:
  a, b = b, a
• Concatenating immutable sequences always results in a new object of the same type as both sequences (the type of the first operand if not same types(?)) - not seeing the intention in enclosing test_list_integer + test_list_float in list()

I prefer

if not <condition>:
    <get out of here>
<operate>

over

if <condition>:
    <operate>
else:
    <get out of here>