sort.go

package algo

// BubbleSort returns a sorted list of integers using the bubble sort algorithm
func BubbleSort(elems []int) []int {
	if elems == nil {
		return nil
	}

	for mx := len(elems) - 1; mx >= 0; mx-- {
		for idx := 1; idx <= mx; idx++ {
			if elems[idx-1] > elems[idx] {
				elems[idx-1], elems[idx] = elems[idx], elems[idx-1]
			}
		}
	}
	return elems
}

// Selection returns a sorted slice using the selection sort algorithm
func Selection(elems []int) []int {
	if elems == nil {
		return nil
	}

	n := len(elems) - 1
	for i := 0; i < n; i++ {
		maxIdx := i
		for j := i + 1; j <= n; j++ {
			if elems[j] < elems[maxIdx] {
				maxIdx = j
			}
		}

		// Now we swap between the min and current if they are different
		elems[i], elems[maxIdx] = elems[maxIdx], elems[i]
	}

	return elems
}

// InsertSort sorts a list of integers using the insert method
func InsertSort(elems []int) []int {
	if elems == nil {
		return nil
	}

	for current := 1; current < len(elems); current++ {
		item := elems[current]
		searchIdx := current
		for ; searchIdx > 0 && elems[searchIdx-1] > item; searchIdx-- {
			elems[searchIdx] = elems[searchIdx-1]
		}
		elems[searchIdx] = item
	}
	return elems
}

sort.py

from typing import List, TypeVar

T = TypeVar('T')


def bubble_sort(elems: List[T]) -> List[T]:
    """Sorts a list using the bubble sort algorithm"""
    if not elems:
        return elems
    
    for mx in range(len(elems), 0, -1):
        for idx in range(1, mx):
            if elems[idx - 1] > elems[idx]:
                elems[idx - 1], elems[idx] = elems[idx], elems[idx - 1]

    return elems


def selection_sort(elems: List[T]) -> List[T]:
    """Sorts a list using the selection sort algorithm"""
    if not elems:
        return elems
    n = len(elems)
    for i in range(0, n):
        smidx = i
        for j in range(i + 1, n):
            if elems[smidx] > elems[j]:
                smidx = j
        elems[i], elems[smidx] = elems[smidx], elems[i]
    return elems


def insert_sort(elems: List[T]) -> List[T]:
    """Sorts a list using the insertion sort algorithm"""
    if not elems:
        return elems
    for idx in range(1, len(elems)):
        search_idx, item = idx, elems[idx]
        while search_idx > 0 and elems[search_idx - 1] > item:
            elems[search_idx] = elems[search_idx - 1]
            search_idx -= 1
        elems[search_idx] = item
    return elems

test_sort.go

package algo

import (
	"testing"
)

func BenchmarkBubbleSort(b *testing.B) {
	for n := 0; n < b.N; n++ {
		var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
		BubbleSort(longSeq)
	}
}

func BenchmarkSelectionSort(b *testing.B) {
	for n := 0; n < b.N; n++ {
		var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
		Selection(longSeq)
	}
}

func BenchmarkInsertSort(b *testing.B) {
	for n := 0; n < b.N; n++ {
		var longSeq = []int{48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26}
		InsertSort(longSeq)
	}
}

test_sort.py

import random
from sorting import *


entry = [48, 41, 23, 97, 36, 12, 78, 47, 62, 74, 69, 42, 94, 82, 35, 5, 7, 68, 73, 83, 49, 11, 56, 70, 8, 2, 24, 52, 89, 37, 50, 93, 61, 88, 91, 60, 95, 32, 29, 9, 28, 79, 30, 99, 45, 27, 19, 55, 46, 72, 96, 81, 14, 86, 22, 1, 63, 3, 34, 31, 59, 58, 66, 65, 80, 84, 92, 20, 75, 25, 67, 64, 90, 33, 18, 44, 54, 40, 38, 16, 98, 77, 71, 51, 4, 21, 53, 43, 87, 57, 39, 6, 76, 13, 10, 15, 85, 17, 26]
expected = list(range(1, 100))

def test_bubble_sort(benchmark):
    assert benchmark(bubble_sort, entry.copy()) == expected

def test_select_sort(benchmark):
    assert benchmark(selection_sort, entry.copy()) == expected

def test_insert_sort(benchmark):
    assert benchmark(insert_sort, entry.copy()) == expected