[Go] Bubble Sort on a slice
Marc
162
GoBubble SortAlgorithm

Hello Gophers! =)

You iterate over a slice and you "bubble up" the "current maximum value".

// bubbleSort sorts the slice `vals` with the
// bubble sort algorithm.
// Time: O(n^2)
// Space: O(1)
func bubbleSort(vals []int) {
	// Time: O(n)
	for i := 1; i < len(vals); i++ {
		// Time: O(n)
		for j := 1; j < len(vals)-i+1; j++ {
			if vals[j-1] > vals[j] {
				vals[j-1], vals[j] = vals[j], vals[j-1]
			}
		}
	}
}

As you can see with the previous answer, we started with i =1 and j = 1 .
We can also start with i =0 and j = 0:

// bubbleSort sorts the slice `vals` with the
// bubble sort algorithm.
// Time: O(n^2)
// Space: O(1)
func bubbleSort(vals []int) {
	// Time: O(n)
	for i := 0; i < len(vals)-1; i++ {
		// Time: O(n)
		for j := 0; j < len(vals)-i-1; j++ {
			if vals[j] > vals[j+1] {
				vals[j], vals[j+1] = vals[j+1], vals[j]
			}
		}
	}
}

Best case scenario (already sorted) is O(n^2).
We could improve it (O(n)) by checking whether the slice is sorted during an iteration:

func bubbleSort(vals []int) {
	// Time: O(n)
	for i := 1; i < len(vals); i++ {
		hasSwapped := false
		// Time: O(n)
		for j := 1; j < len(vals)-i+1; j++ {
			// Time: O(1)
			if vals[j-1] > vals[j] {
				vals[j-1], vals[j] = vals[j], vals[j-1]
				hasSwapped = true
			}
		}
		// Time: O(1)
		if !hasSwapped {
			return
		}
	}
}

If you want to test in Go Playground with print:

package main

import "fmt"

// Time: O(n^2)
// Space: O(1)
func main() {
	vals := []int{3, 1, 5, 2, 8, 9, 0}
	bubbleSortAndPrint(vals)
}

func bubbleSortAndPrint(vals []int) {
	fmt.Println(" i  j  vals ")
	// Time: O(n)
	for i := 1; i < len(vals); i++ {
		hasSwapped := false
		// Time: O(n)
		for j := 1; j < len(vals)-i+1; j++ {
			fmt.Printf(" %v ", i)
			fmt.Printf(" %v  ", j)
			// Time: O(1)
			if vals[j-1] > vals[j] {
				vals[j-1], vals[j] = vals[j], vals[j-1]
				hasSwapped = true
			}
			fmt.Printf("%v \n", vals)
		}
		// Time: O(1)
		if !hasSwapped {
			return
		}
	}
}

The logic is the same for linked lists.

Note (for interview)

If you cannot use the standard library and if you are not asked to implement this specific algorithm, use a better one where the time complexity is O(nlogn).

See all sorting and searching algorithms here (WIP):

If you can, use the sort package of Go's Standard library:

package main

import (
	"sort"
)

func main() {
	// Slice of int
	ints := []int{4, 2, 1, 5, 3, 0}
	sort.Ints(ints)

	// Slice of float64
	floats := []float64{5.2, -1.3, 0.7, -3.8, 2.6}
	sort.Float64s(floats)

	// Slice of string
	strings := []string{"Go", "Bravo", "Gopher", "Alpha", "Grin", "Delta"}
	sort.Strings(strings)

	// Slice of struct
	type person struct {
		name string
		age  int
	}
	person1 := person{"max", 28}
	person2 := person{"eliot", 4}
	person3 := person{"gaby", 27}
	persons := []person{person1, person2, person3}
	sort.Slice(persons, func(i, j int) bool {
		return persons[i].age < persons[j].age
	})
}

Go playground with print here.

Make sure you know the time and space complexity of the language's default sorting algorithm for interviews.
Go uses QuickSort.

I hope it can help!

Comments (0)