If you want to become a good programmer, you need to learn to think like one. And the number one way to train your programmer thinking is through training your understanding of algorithms, specific functions designed to solve a well-defined computational problem.
In this 4-part series, we’ll go through one of the most fundamental computational problems in computer science, sorting an array of numbers, and use that as a basis to explore several important algorithms. The algorithm I’ll be sharing today is the most intuitive and easy-to-understand sorting algorithm, and it will get more and more advanced from here on. Let’s first take a deeper look at the computational problem.
Given an array of numbers, write a function that will sort the numbers in ascending order. The function will modify the array itself (no return value).
input = [3, 2, 5, 4, 1, 6]
output = [1, 2, 3, 4, 5, 6]
Take a minute to think about how you would approach this problem. Try to work out the steps in your head. You could even try coding it on your local IDE if you’re feeling extra committed.
This problem itself isn’t actually that hard in it of itself, and an experienced programmer could probably figure out a solution (in his/her head) in under 3 minutes. The instructional value of the problem really arises when you try to search for more efficient ways of solving it.
However, to a complete beginner, this problem can be pretty challenging, so it’s totally normal if you just started learning to code and are struggling with it.
If you did come up with a solution, it’s probably pretty intuitive and fairly similar to the algorithm we’re going to look at in this article.
Bubble Sort is the most intuitive sorting algorithm. The algorithm starts with looping through the array. If a number in the array is greater than the number following it (mispositioned), it swaps the numbers around. One loop represents one “round” in the visual below.
[3, 2, 5, 4, 1, 6] // starting arrayRound 1:
[2, 3, 5, 4, 1, 6]
[2, 3, 4, 5, 1, 6]
[2, 3, 4, 1, 5, 6]Round 2:
[2, 3, 1, 4, 5, 6]
[2, 1, 3, 4, 5, 6]Round 3:
[1, 2, 3, 4, 5, 6]
The algorithm keeps looping through the array until it notices that none of the numbers are mispositioned anymore, meaning the array is sorted.
The name “Bubble Sort” comes from how the smaller numbers in the array appear to bubble to the top of the array.
The outside loop (i) are the “rounds” mentioned above. The variable changed keeps track of whether anything was changed in the round. If nothing was changed, the algorithm will know that the sorting is done and break out of the loop without wasting extra time.
The inside loop (j) is the pointer that determines if the numbers in the array are mispositioned. As j is incremented, array[j] and array [j + 1] are checked. If they are found to be mispositioned, the array[j] and array[j + 1] are switched.
def bubble_sort(array):
for i in range(len(array) - 1):
changed = Falsefor j in range(0, len(array) - 1):
if array[j + 1] < array[j]:
array[j], array[j + 1] = array[j + 1], array[j]
changed = Trueif changed == False:
breaknums = [2, 3, 6, 4, 1, 5]
bubble_sort(nums)
print(nums) # [1, 2, 3, 4, 5, 6]
function bubbleSort(array) {
let copy;
for (let i = 0; i < array.length - 1; i ++) {
let changed = falsefor (let j = 0; j < array.length - 1; j ++) {
if (array[j + 1] < array[j]) {
// In Javascript, there isn't the "a, b = b, a" shorthand
copy = array[j]
array[j] = array[j + 1]
array[j + 1] = copy
changed = true
}
}
if (changed == false) {
break
}
}
}
let nums = [2, 3, 6, 4, 1, 5]
bubbleSort(nums)
console.log(nums) // [1, 2, 3, 4, 5, 6]
In the best case, the array is already sorted at the beginning. This means we’ll only have to run the inner loop once before the algorithm realizes that the array is already sorted. Since the inner loop repeats n-1 times (n being the length of the input array), the best case time complexity is O (n).
In an average case, the inner loop and outer loop can both be seen as proportional to n, so the average case time complexity is O (n²).
In the worst case, both loops run n-1 times, giving a worst case time complexity of O(n²).
For space complexity, the algorithm only changes the values in the input array without adding anything new, which doesn’t use any extra memory. The algorithm stores one variable used to store a temporary copy of array[j] so the algorithm has a space complexity of O(1).
Bubbling is by far the most intuitive sorting algorithm, usually the first solution programmers will think of. However, the algorithm is honestly pretty slow. A complexity of O(n²) is just not good enough when you’re working with large-scale projects with tons of data.
In the next article of the Sorting Algorithms series, we’ll try to see if we can improve our time complexity… maybe make thinks a little quicker.