Bubble Sort
August 12, 2019
Code Snippets
Classic sorting algorithm for sorting items.
Written in Python, this is my take on the algorithm, it looks a bit different than other examples. Most likely, this is due to my desire to abort processing as early as I can with the “vars for optimization”…
def bubble_sort(arr): # BigO == n^2 # 0 Elements: Exception if len(arr) == 0: raise Exception('No Elements') # 1 Element: Early Return if len(arr) == 1: return arr # vars for optimization numItems = len(arr) numPasses = 1 sortMade = True # perform until no swaps made while sortMade: sortMade = False maxChecks = numItems-numPasses for x in range(maxChecks): if arr[x] > arr[x+1]: val = arr[x] arr[x] = arr[x+1] arr[x+1] = val sortMade = True numPasses += 1 return arr
TESTS! Anytime the function has simple ins/outs and a well defined use, there’s no excuse to not have tests.
import pytest import random from bubble_sort import bubble_sort def test_func_exists(): bubble_sort([1]) def test_sort(): input = [1,5,3,2,4] actual = bubble_sort(input) expected = [1,2,3,4,5] assert actual == expected def test_all_same(): input = [3,3,3,3,3,3,3] actual = bubble_sort(input) expected = [3,3,3,3,3,3,3] assert actual == expected def test_sort_zero(): with pytest.raises(Exception): bubble_sort([]) def test_sort_lots(): input = [] for x in range(1000): input.append(random.randint(1,1000)) actual = bubble_sort(input) expected = input expected.sort() assert actual == expected