June 1st 2020
I’m an engineer with a great interest in programming!
Have you ever felt overwhelmed by an algorithm problem and don’t know where to start?
One thing I like to do when programming, is to understand the problem before I get to program. Otherwise, if I try to get the logic on the go, I usually end up having to debug what the hell is happenning in the program and adapt to those outputs.
The dissadvantage of doing so are: it’s a loss of time, and you probably won’t be able to explain to another person why does your program works with all the adjustments you had to do to it.
So let’s start applying the 4 steps in the image above for sorting an array of numbers from smallest to largest.
First step is to decompose, it would seem a big problem to sort everything in one go: how will we be able to compare everything against everything?
There are many ways to approach this problem, but for this example, we will use a simple sorting algorithm ‘the bubble sort’. It is called bubble sort because the biggest numbers are the first to move to the correct place, and they go up like bubbles in the water.
So lets start from the smallest step to the most general one:
1.- Compare 2 numbers, find the biggest, and ensure it is to the right.
2.- Repeat the comparisons until you finish with the array, as a result, the biggest number to be moved will be the first one to be in the right place.
3.- Repeat the passes through the array until all ‘local’ biggest numbers are in the right place. In other words, until we finish sorting.
Here is how the array will be changing:
For pattern matching we can realize that we repeat the smallest step ‘comparisons’ as many times as needed, so that should be inside a loop that repeats until we finish one pass. And we also see that we repeat the passes through the array until we are done sorting, that is another loop.
In abstractions we need to take out special cases, for example, in the gif above, you can see I don’t compare until the very end of the array:
I compare positions 0-1 until positions 9-10, (I’m using index 0 convention)
next time I compare from 0-1 to 8-9,
next time from 0-1 to 5-6,
next time from 0-1 to 3-4,
next time from 0-1 to 2-3
and then I know I finished sorting
I don’t go through the whole array because it is not necessary since I already know that the last numbers are already sorted. But it will not always be with these specific positions, so we have to think, what would be a general rule that could apply to any array?
My solution is to use a variable that stores the position where I made the last change in one pass of the array; I can be sure that everything to the right of the last change will already be sorted and I don’t need to check those numbers again, this saves computing time 🙂
And the final part! the algorithm.
I created 2 variables:
to know where I have finished with the array, my limit
to save the last change, the one I talked about in the previous section.
How do I determine my limit? Easy, just count the pairs for the first pass through the array, the one that considers all pairs.
(I will be using ruby code to illustrate)
len = arr.size - 1 # len = 11-1 = 10. consider I will use a exclusive range, # so it will only include 0,1,2,3,4,5,6,7,8,9.
The value for the last change will be set everytime we make a swap, that will come later, for now, let’s set it to position 0
position = 0
for the last changed position.
if arr[i] > arr[i + 1] arr[i], arr[i + 1] = arr[i + 1], arr[i] position = i end
is the current position in the array, in this case, it’s 0. And
is the next position (to compare against), in this case position 1. In ruby we can use
arr[i], arr[i+1] = arr[i+1], arr[i]
to swap positions of the elements in the array.
let temp = arr[i] arr[i] = arr[i+1] arr[i+1] = temp
to do the swap only when the first element is greater than the next, otherwise, we don’t want to modify anything, so I end the
, the limit.
variable changes until position 8, because it didn’t make any movements when it was in the 9 iteration
for(var i = 0, i < len, i++)
len.times do |i| if arr[i] > arr[i + 1] arr[i], arr[i + 1] = arr[i + 1], arr[i] position = i end end
We want that our new limit for the next time we do this again will be the last position we changed previously, so we assign it to our len. (a)
position = 0
at the beginning of each repetition. (b)
We will also tell our biggest loop to do this while our len is more or equal than 1, because we want to stop when we are left with a pair of elements that we know are already sorted, element 0 and element 1 when len is 0. (c)
while len >= 1 #<--------------(c) position = 0 #<--------------(b) len.times do |i| if arr[i] > arr[i + 1] arr[i], arr[i + 1] = arr[i + 1], arr[i] position = i end end len = position #<--------------(a) end
Finally, we return the modified array, and the complete code will be the following:
def bubble_sort(arr) len = arr.size - 1 while len >= 1 position = 0 len.times do |i| if arr[i] > arr[i + 1] arr[i], arr[i + 1] = arr[i + 1], arr[i] position = i end end len = position end arr end print bubble_sort [10, 4, 6, 8, 5, 2, 4, 6, 8, 9, 22] # [ 2, 4, 4, 5, 6, 6, 8, 8, 9,10, 22]
I hope this can help you as a guide to start thinking about programming solutions in the future. Thanks for reading until here 🙂
I will leave you with a little animation representing the process that happens with the array and the variables: