package main
import (
"fmt"
"time"
)
// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
func bubbleSort(arr []int) []int {
length := len(arr)
items := make([]int, length)
copy(items, arr)
for end := length; end > 1; end-- {
swapped := false
for j := 1; j < end; j++ {
if items[j] < items[j-1] {
var tmp = items[j]
items[j] = items[j-1]
items[j-1] = tmp
swapped = true
}
}
if !swapped {
break
}
}
return items
}
func main() {
items := []int{4, 1, 5, 3, 2}
sortItems := bubbleSort(items)
// sortItems is {1, 2, 3, 4, 5}
// *** simplified speed test ***
items = make([]int, 200)
for i := 0; i < len(items); i++ {
items[i] = len(items) - 1 - i
}
count := 10000
start := time.Now()
for i := 0; i < count; i++ {
bubbleSort(items)
}
delta := time.Now().Sub(start)
milliseconds := delta.Milliseconds()
fmt.Println(sortItems)
fmt.Println(milliseconds, "milliseconds")
// about 188 milliseconds
}