Bubble Sort Algorithm: How to Develop Your Computational Thinking

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 improvising on the way 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.

Decompose: Break down a problem into smaller pieces

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:

Pattern matching: Finding similarities between things

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.

Abstractions: Pull out specific differences to make one general solution

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

Why? How?

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 :)

Algorithm: List of steps to complete a task

And the final part! the algorithm.

I created 2 variables:

len

to know where I have finished with the array, my limit

position

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

Then make the comparison and swap the elements accordingly, don't forget to update your variable

position

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

i+1

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.

In javascript the swap can be done like this:

let temp = arr[i]
arr[i] = arr[i+1]
arr[i+1] = temp

Use an

if

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

if

Then we repeat until we finish passing through the array... until

len

, the limit.

Notice how

position

variable changes until position 8, because it didn't make any movements when it was in the 9 iteration

In the code it is represented with a loop, I use

#times

method in ruby, but you could represent it in other languages as javascript like:

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)

And the next time we repeat this process we want to begin with a reseted position so it can be used again, thus we assign

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: