Classic CS algorithm in Python, annotated with lots of comments
Quick Sort is one of those algorithms that seems unnaturally complex at first, but once its steps are broken down piece by piece the logic is easy to follow.If you haven’t heard of this algorithm, please read on. If you’re here on a whim, I hope you find this article to be a good review.
Setting Up Your Sort
The foundations of the quick sort algorithm lie in its inputs. For this exercise, we will be using a recursive function, so it’s important for us to define our variables with precision. The Quick Sort function operates on three fundamentals
2. Creating Partitions
The Recursive Function
How does quick sort arrange an array of numbers? The way that this happens is not so straightforward, and is not something a person would think of through common sense.
Here’s what happens, basically:
1. The quick sort function relies upon a value that’s commonly referred to as the PIVOT in order to arrange its values. The pivot serves as the function’s key to compares values against. We’ll use this value to compare against the LEFT and RIGHT values, which we’ll define in step 2
2. Next, we’ll define LEFT and RIGHT – We’ll be comparing these values to our pivot and SWAPPING them. And how do we define these value? Starting from the LEFT side of the array, we count up the array until we reach a value that larger than our pivot. It’s important to note that these variables should be saved as INDEX, and not VALUE. We are comparing the VALUE of the list to the PIVOT value, but are tracking the INDEX into LEFT We do the same starting from the right, counting left. Once we find our values, we perform a SWAP, where left and right are replaced. We continue doing this until the array index for LEFT is greater than the array index for for RIGHT.
3. Once our LEFT index is greater than our RIGHT index, we need to PARTITION. What does it mean to partition? Creating a partition is the act of taking something large (like a data set) and splitting it into smaller pieces, deliberately. We’ll be slicing our lists into smaller pieces, and running them through our quick sort function.
Quick sort is a fairly complex algorithm, so don’t be worried if the structure of the function is not clear after a single read through.It seems like it’s easiest break this function out into three parts while building it:
1. Recursive Function
2. Partition Function
import random def _partition(arr: list, start, end: int) -> int: # Start at the Start scout = wagon = start # Pick a pivot point (choose: first, end, middle) # @TODO: get fancy, pick 3 random ints from array # and use the middle value's index as pivot pivot = arr[end] # Continue until Scout is at end while scout < end: # is the value less-than pivot? if arr[scout] < pivot: # swap scout for wagon, vice versa arr[wagon], arr[scout] = arr[scout], arr[wagon] # adv wagon wagon += 1 # move scout forward scout += 1 # final swap arr[wagon], arr[end] = arr[end], arr[wagon] return wagon def _quick_sort(arr: list, start, end: int) -> list: # are we overlapped? If so ,we are done, as it means # we have processed everything if start > end: return arr # Pick a point pos = _partition(arr, start, end) # Call ourselves again with the "left" and "right" side of pos _quick_sort(arr, start, pos-1) _quick_sort(arr, pos+1, end) return arr def quick_sort(arr: list) -> list: # BigO (n log n) # :: log n, as this is a divide algo # :: n, as we need to merge the halfs back # 0 Elements: Exception if len(arr) == 0: raise Exception('No Elements') # 1 Element: Early Return if len(arr) == 1: return arr # Do It!!!! random.seed() arr = _quick_sort(arr, 0, len(arr)-1) return arr
import pytest import random from quick_sort import quick_sort def test_func_exists(): quick_sort() def test_sort(): input = [5,15,3,9,10] actual = quick_sort(input) expected = [3,5,9,10,15] # assert actual == expected assert True == False def test_sort(): input = [1, 5, 3, 2, 4] actual = quick_sort(input) expected = [1, 2, 3, 4, 5] # assert True == False assert actual == expected def test_all_same(): input = [3, 3, 3, 3, 3, 3, 3] actual = quick_sort(input) expected = [3, 3, 3, 3, 3, 3, 3] assert actual == expected def test_sort_zero(): with pytest.raises(Exception): quick_sort() def test_sort_lots(): input =  for x in range(1000): input.append(random.randint(1, 1000)) actual = quick_sort(input) expected = input expected.sort() assert actual == expected