Writing Algorithms with Go Part 1
Implement bubble sort in Go.
One of the things I’m doing to stay productive while on quarantine is learning Go — an open source programming language developed at Google. As a data scientist, I find learning Go useful in building production-ready ML models and AI products in general. Although, in bigger, more structured companies, deployment seems to be out of a data scientist’s scope, a lot of startups prefer data scientists that knows a thing or two about deployment practices. If you’re looking to work at a company that uses Google Cloud for their infrastructure, like Spotify, then Go is worth the shot.
This article will be the first in a series of tutorials on how to implement algorithms such as sorting and searching using Go. I will assume that the reader knows basic data types and functions in Go and have prior programming experience in any language.
Bubble Sort
Sorting is a task where elements of a list will be put in a certain order. Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
How it works:
- Pass through the list, compare the values of each adjacent pair in the list
- For each adjacent pair, swap the values if they are in the wrong order.
- Repeat 1 and 2 until no swaps are made in a pass.
Suppose that we want to sort the list of integers below in ascending order.
[33, 91, 76, 8, 22]
We start off by looking at each pair of adjacent integers (1st int and 2nd int, 2nd int and 3rd int, and so on).
- For the first pair, 33 and 91, no swapping of values is necessary as the two are already in ascending order.
- We then go on to the next pair, 91 and 76. Here, the values will be swapped since they are not in ascending order. The resulting list will be: [33, 76, 91, 8, 22]
- The next pair, 91 and 8 needs to be swapped as well. [33, 76, 8, 91, 22]
- The last pair, 91 and 22, will also be swapped. [33, 76, 8, 22, 91]
Notice that this first pass floats the largest value to the top of the list like a bubble, hence the name. We will repeat the steps above until the entire list is sorted.
Implementation in Go
We’ll start off by creating the pass function which will go through each adjacent pair of elements in a given list.
The pass function, accepts an array of integers, list, and a boolean value, ascending, which corresponds to the direction of sorting we prefer. When called, this function will go through the array of integers and compare each adjacent pair, firstElement and secondElement . The elements in a pair will be swapped if it’s not in the desired order based on the boolean value,ascending .
swap function accepts an array of integers, list , and the index of the first element of the pair, firstIndex . The swap is very similar to Python’s a,b=b,a style of swapping. An explanation to how this works is here.
The bubblesort function will wrap everything up.
It accepts an array of integers, list , and a boolean value, ascending for the direction of the sort. The number of passes is set to N-1 to make sure that all cards will be floated to the top in the right order. We can also set it to N but there’s no need to pass over the list the Nth time as no swaps will be made. The count variable keeps track of the number of passes performed by the algorithm before stopping. You wouldn’t appreciate its use case at this stage but if we try to optimize bubble sort, we will see that the number of passes decreases.
Finally, let’s try it out by building the main function. Declare the array of integers and the direction of the sort and call bubblesort function.
Running the entire code will print the following:
Original list: [33 91 76 8 22]
Number of iterations: 4
Sorted list: [8 22 33 76 91]Optimization
There’s probably a lot of ways to optimize bubble sort, but one way I can think of is to stop the algorithm if there’s only 1 swap done on the pass. Consider the almost sorted list of integers below:
[8, 22, 76, 33, 91].
Notice that we only needed to pass over the list once to sort it in ascending order instead of going over the list N-1 times (4 times). Let’s modify bubblesort and pass functions to implement this optimization.
Here’s the modified pass function. Here we added a new variable swapCount to count the number of swaps in each pass.
We’ll use swapCount in the modified bubblesort function like so:
The algorithm will stop if swapCount is equal to 1.
If we sort the list, [8, 22, 76, 33, 91], in ascending order without optimizing the algorithm, it will pass through the list 4 times ( N-1 ).
Original list: [8 22 76 33 91]
Number of iterations: 4
Sorted list: [8 22 33 76 91]Optimizing decreases the number of iterations needed.
Original list: [8 22 76 33 91]
Number of iterations: 1
Sorted list: [8 22 33 76 91]The entire code is here. Let me know in the comments if you have any other ways to optimize the algorithms.
References
[1] Sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm
[2] Bubble sort, https://en.wikipedia.org/wiki/Bubble_sort
[3] Swap two number in golang, https://stackoverflow.com/questions/35707222/swap-two-numbers-golang/35707958
