# Quick Sort Algorithm (Python)

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

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

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>

• 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. Commented Sep 28, 2019 at 12:34
• Concatenating immutable sequences always results in a new object This also applies to lists, which is the case here.
– GZ0
Commented Sep 28, 2019 at 14:41