Tonight I’m looking at some sorting algorithms in Python. First up are Bubble Sort and Selection sort, both with average and worst case runtime, and memory. Then I’ll look at an iterative and recursive implementation of Merge Sort, Quick Sort, and Heap Sort with .

# Bubble Sort

This algorithm walks through a list several times, swapping consecutive out-of-order elements as it sees them. The worst case is when the list is in descending order when you want it ascending. The outer for-loop might look unnecessary, but go ahead, take it out and see what happens. You’ll see why this one is .

def bubbleSort(x): n = len(x) if n <= 1: return x for _ in range(n): for i in range(1,n): # if the prev element > next element if x[i-1] > x[i]: # make the swap x[i-1], x[i] = x[i], x[i-1] return x assert bubbleSort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]

# Selection Sort

While Bubble Sort is unexpectedly expensive with its outer for-loop, Selection Sort is unexpectedly complex compared to its description. Selection Sort works by finding the smallest element, and swapping it out for the first element. Then it finds the smallest element starting from the second element to the end, and then it swaps that smallest element for the second element, and so on. Here’s what I worked out. (The variable name `cursor`

was pretty random, but I couldn’t deal with another single-letter-variable.)

def selectionSort(x): n = len(x) if n <= 1: return x for i in range(n): cursor = i for j in range(i,n): # find the smallest element if x[j] < x[cursor]: cursor = j # make the swap x[i], x[cursor] = x[cursor], x[i] return x assert selectionSort([5, 4, 3, 2, 1]) == [1, 2, 3, 4, 5]

# Merge Sort

This one was tricky. This book I’m reading says that, “Okay, so first you split everything up and then you just merge things back together and sort them as you go and, like, voila.” The trick is that you do two recursive calls in the same function. I’d never seen that before. It felt like seeing someone castle for the first time. Anyway, I did an iterative version also, because Python by design doesn’t like recursion.

def merge(a, b): x = [] while len(a) > 0 and len(b) > 0: if a[0] < b[0]: x.append(a.pop(0)) else: x.append(b.pop(0)) while len(a) > 0: x.append(a.pop(0)) while len(b) > 0: x.append(b.pop(0)) return x def halve(x): half = len(x) / 2 return x[:half], x[half:] def recursiveMergeSort(x): if len(x) == 1: return x a, b = halve(x) a = recursiveMergeSort(a) b = recursiveMergeSort(b) return merge(a, b) def iterativeMergeSort(x): queue = [[i] for i in x] while len( queue ) > 1: a, b = queue.pop(0), queue.pop(0) queue.append(merge(a, b)) return queue[0] x = [40, 82, 97, 47, 7] assert recursiveMergeSort(x) == [7, 40, 47, 82, 97] assert iterativeMergeSort(x) == [7, 40, 47, 82, 97]

# Quick Sort

import random def pivot(x): return random.randint(0, len(x) - 1) def partition(x): if len(x) == 2: lt = [min(x)] gt = [max(x)] else: pvt = pivot( x ) lt = [i for i in x if i <= pvt] gt = [i for i in x if i > pvt] return lt, gt def quicksort(x): if len(x) < 2: return x lt, gt = partition(x) lt = quicksort(lt) gt = quicksort(gt) return lt+gt assert quicksort([0]) == [0] assert quicksort([0, 0]) == [0, 0] assert quicksort([0, 1]) == [0, 1] assert quicksort([1, 0]) == [0, 1]

# Heap Sort

Heap sort enjoys for best, average, and worst cases.

from typing import * from dataclasses import dataclass, field @dataclass class Heap: A: List[int] def swap(self, i, j): print('\nSwap indices {} and {}'.format(i, j)) self.A[i], self.A[j] = self.A[j], self.A[i] print('{}'.format(self.A)) def sort(self): print('Sorting: {}'.format(self.A)) self.build_heap() print('\n' + '-' * 40) N = len(self.A) for i in range(N - 1, -1, -1): print('\nIndex: {}'.format(i)) self.swap(0, i) self.heapify(0, i) return self.A def build_heap(self): N = len(self.A) for i in range(N // 2 - 1, -1, -1): self.heapify(i, N) def heapify(self, idx, maximum): print('heapify({}, {})'.format(idx, maximum)) largest = idx left = 2 * idx + 1 right = 2 * idx + 2 if left < maximum and self.A[left] > self.A[idx]: largest = left if right < maximum and self.A[right] > self.A[largest]: largest = right if largest != idx: self.swap(idx, largest) self.heapify(largest, maximum) assert Heap([8, 11, 9, 2, 10, 16]).sort() == [2, 8, 9, 10, 11, 16]