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(×ばつ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>

• 301_Moved_Permanently: I'd stress the first point even more by saying that a return value imply a new object, since modifying it in place does not invalidate the reference held by the caller. But here, the input is modified in place AND returned, which is confusing at best if not error prone.
• GZ0: Concatenating immutable sequences always results in a new object This also applies to lists, which is the case here.