Bubble Sort in Go

Published on 30 September 2020 (Updated: 30 September 2020)

Bubble Sort in Go

In this article, we’ll be tackling Bubble Sort in Go.

How to Implement the Solution

At this point, let’s dig into the code a bit. The following sections break down the Bubble Sort in Go functionality.

Solution

package main

import (
	"encoding/json"
	"fmt"
	"os"
	"regexp"
	"strconv"
	"strings"
)

func bubbleSort(list []int) []int {
	swapped := true
	for swapped {
		swapped = false
		for i := 0; i < len(list)-1; i++ {
			if list[i] > list[i+1] {
				n := list[i]
				list[i] = list[i+1]
				list[i+1] = n
				swapped = true
			}
		}
	}
	return list
}

func swap(list []int, firstIndex int, secondIndex int) bool {
	if list[firstIndex] > list[secondIndex] {
		x := list[firstIndex]
		list[firstIndex] = list[secondIndex]
		list[secondIndex] = x
		return true
	}
	return false
}

func strToSliceInt(strList string) []int {
	list := regexp.MustCompile(", ?").Split(strList, -1)
	if len(list) < 2 {
		exitWithError()
	}
	var nums []int
	for _, num := range list {
		n, err := strconv.Atoi(num)
		if err != nil {
			exitWithError()
		}
		nums = append(nums, n)
	}
	return nums
}

func sliceIntToString(list []int) (out string) {
	bytes, _ := json.Marshal(list)
	out = strings.Replace(string(bytes), ",", ", ", -1)
	out = strings.Trim(out, "[]")
	return
}

func exitWithError() {
	fmt.Println("Usage: please provide a list of at least two integers to sort in the format \"1, 2, 3, 4, 5\"")
	os.Exit(1)
}

func main() {
	if len(os.Args) != 2 {
		exitWithError()
	}

	nums := strToSliceInt(os.Args[1])
	nums = bubbleSort(nums)
	fmt.Println(sliceIntToString(nums))
}

The Main Function

Breaking down this solution bottom up,

func main() {
	if len(os.Args) != 2 {
		exitWithError()
	}

	nums := strToSliceInt(os.Args[1])
	nums = bubbleSort(nums)
	fmt.Println(sliceIntToString(nums))
}

This is the main function of this file. It parses the form Args, assures that there is enough elements for it to be sorted, the converts the string to integers, then calls our bubble sort function, and finally prints the results. It also deals with any errors raised.

Transform Input Parameters

func strToSliceInt(strList string) []int {
	list := regexp.MustCompile(", ?").Split(strList, -1)
	if len(list) < 2 {
		exitWithError()
	}
	var nums []int
	for _, num := range list {
		n, err := strconv.Atoi(num)
		if err != nil {
			exitWithError()
		}
		nums = append(nums, n)
	}
	return nums
}

This function takes a string like "2, 1, 10, 5, 3", and turns into a list of numbers. It does this using a list comprehension, first we need to convert our string into a list Split(strList, -1) which is a list of strings split by comma (,). So our original input string becomes ["2", " 1", " 10", " 5", " 3"]. Then for each element in the list for _, num := ... , we do something to it.

In this example we convert it into a decimal integer, strconv.Atoi(num). After that each of the newly converted integers are converted added to the new list nums.

func sliceIntToString(list []int) (out string) {
	bytes, _ := json.Marshal(list)
	out = strings.Replace(string(bytes), ",", ", ", -1)
	out = strings.Trim(out, "[]")
	return
}

This function takes a list of integers like [2, 1, 10, 5, 3], and turns into a string. It does this using a list comprehension, first we need to convert our list of integers into a string bytes, _ := json.Marshal(list). So our original input string becomes "[2,1,10,5,3]". Then we replace the commas with commas and a space "[2, 1, 10, 5, 3]". Finally, we remove the square brackets before returning the string out = strings.Trim(out, "[]").

Throw Errors

func exitWithError() {
	fmt.Println("Usage: please provide a list of at least two integers to sort in the format \"1, 2, 3, 4, 5\"")
	os.Exit(1)
}

This function prints a message and then exits the script with an error, os.exit(1). If any non-zero value is returned then the program didn’t complete properly. This function is called if the user input isn’t correct.

Bubble Sort

func bubbleSort(list []int) []int {
	swapped := true
	for swapped {
		swapped = false
		for i := 0; i < len(list)-1; i++ {
			if list[i] > list[i+1] {
				n := list[i]
				list[i] = list[i+1]
				list[i+1] = n
				swapped = true
			}
		}
	}
	return list
}

Finally we’re at the real meat and potatoes of the script. This function takes an unsorted integer list and returns a sorted list, using the bubble sort algorithm. This function bubbleSort has two nested for loops inside pof it. For swapped will run as long as the variable gets swapped in each run of the loop. The for loop nested inside will run from the first element in the list(i=0) to the last minus one(len(list)-1). As it runs through it compares every element to the one after it and if it is larger it swaps them n := list[i] list[i] = list[i+1] list[i+1] = n and after that it marks swapped true to notify the outer loop it should keep running. If stopped were not changed to true the list would stop there because it checked every element and determined none of them needed to be moved.

For example, if [3, 2, 5, 1] is the input:

How to Run Solution

If we want to run this program, we should probably download a copy of Bubble Sort in Go. After that, we should make sure we have the latest Go interpreter. From there, we can run the following command in the terminal:

go run bubble-sort.go "3, 2, 10, 6, 1, 7"

Alternatively, we can copy the solution into an online Go interpreter and hit run.

Further Reading