Skip to content

Instantly share code, notes, and snippets.

@cprieto
Created May 7, 2020 13:38
Show Gist options
  • Save cprieto/f6d58d767280f87194fde52b6baeb155 to your computer and use it in GitHub Desktop.
Save cprieto/f6d58d767280f87194fde52b6baeb155 to your computer and use it in GitHub Desktop.
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
}
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
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)
}
}
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment