Marvin "Vin" Colgin

Full-Stack Developer

Back-End Expert

Team Lead

Business Owner

React Enthusiast

Node.JS Lover

Marvin "Vin" Colgin

Full-Stack Developer

Back-End Expert

Team Lead

Business Owner

React Enthusiast

Node.JS Lover

Blog Post

Quicksort

August 14, 2019 Code Snippets

Classic CS algorithm in Python, annotated with lots of comments

Introduction

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   

1. Recursion
2. Creating Partitions
3. Swapping

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.

Straightforward right?

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
   3. Swapping

Code

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

Tests…

import pytest
import random
from quick_sort import quick_sort


def test_func_exists():
    quick_sort([1])

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
Write a comment