Quick Sort
S
M
D
p
O
A
R
P
"""
A pure Python implementation of the quick sort algorithm
For doctests run following command:
python3 -m doctest -v quick_sort.py
For manual testing run:
python3 quick_sort.py
"""
from __future__ import annotations
from random import randrange
from typing import Any, Protocol
class Comparable(Protocol):
def __lt__(self, other: Any, /) -> bool: ...
def quick_sort[T: Comparable](collection: list[T]) -> list[T]:
"""A pure Python implementation of quicksort algorithm.
:param collection: a mutable collection of comparable items
:return: the same collection ordered in ascending order
Examples:
>>> quick_sort([0, 5, 3, 2, 2])
[0, 2, 2, 3, 5]
>>> quick_sort([])
[]
>>> quick_sort([-2, 5, 0, -45])
[-45, -2, 0, 5]
>>> quick_sort(["z", "a", "m", "b"])
['a', 'b', 'm', 'z']
>>> quick_sort([3.14, -1.0, 2.71])
[-1.0, 2.71, 3.14]
>>> quick_sort([0, 5, 3, 2, 2]) == sorted([0, 5, 3, 2, 2])
True
>>> quick_sort(["z", "a", "m"]) == sorted(["z", "a", "m"])
True
"""
if len(collection) < 2:
return collection
pivot_index = randrange(len(collection))
pivot = collection[pivot_index]
lesser = [item for item in collection if item < pivot]
equal = [item for item in collection if item == pivot]
greater = [item for item in collection if item > pivot]
return [*quick_sort(lesser), *equal, *quick_sort(greater)]
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n").strip()
unsorted = [int(item) for item in user_input.split(",")]
print(quick_sort(unsorted))
About this Algorithm
Problem Statement
Given an unsorted array of n elements, write a function to sort the array
Approach
- Make the right-most index value pivot
- partition the array using pivot value
- quicksort left partition recursively
- quicksort right partition recursively
Time Complexity
O(n^2)Worst case performanceO(n log n)Best-case performanceO(n log n)Average performance
Space Complexity
O(log n) Worst case
Founder's Name
Tony Hoare in 1959
Example
arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes: 0 1 2 3 4 5 6
low = 0, high = 6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1
Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j
// are same
j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30
j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]
j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j]
i = 3
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped
We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot)
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped
Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.
