Bubble Sort

The first sort has the friendly title of bubble sort as the high numbers at the bottom of the list bubble up to the top like bubbles in water. The first thing to do is write out the simplest case so you can picture how it would work (if you are super smart then you can jump ahead to the maths).

List – 2 values

The simplest list would be 2 numbers: 34, 95

Although there are are only two numbers there’s more information here that we’ll use in all the sorting and searching algorithms. Lists have a length (number of values in the list) and values in the list have a position. The positions of those values are both absolute and relative. Absolute values are the number in the list (number 3 is the queue) and relative values (number 3 is after number 2 and before number 4). The length and position of things in the list is important for sorting as the things in the list are not often numbers but words. For example a list of name of students that you want to sort alphabetically.

As humans when we look at a list we number it like this

If asked where in the list is position 36 you’d say at position 1 and 94 is at 2 or next to 36. Labelling where things are relative to another thing in an order is a called an index. In a book an index is a list of terms in alphabetical order. Labelling positions 1 and 2 is indexing the list. We can index a list in anyway we want but we normally start at one. With computer programs we can start at zero or one. The most common programming (Python, C, C++, Java) use zero as the starting value. Starting our paired list at zero we get the following.

Why does it matter starting at zero? The advantage is in this list we don’t care about the count but the position of values. 94 is not the second value in the list; it is the first one after the initial value. It is +1 away from the start. To get to 96 move +1 up from 36. For the above list the length is 2 and it has values from position 0 to 1.

With this information we can start to look at the logic to sort this list. For our example list the logic would be:

If value at index 0 > value at index 0+1 is True then:
value at index 0 = value at index 0+1
value at index 0+1 = value at index 0
else (index 0 < index 0+1):
end

If we run this through our example list:

If 94 > 36 is True then:
94 = index 0+1
36 = index 0
else:
end

This leaves the list looking like this

The list is now sorted from lowest to highest in terms of number size. If we look at the list vertically instead of horizontally then you can see why it’s called a bubble sort.

This makes sense for a human but there is a problem for a computer. We can’t swap the values in two steps as we’d be referencing the change just made so we have to do it at the same time. The python code for this swap looks like this:

# Before swap
list_1 =[94, 36]
print (list_1)
print(list_1[0])
print(list_1[1])

if list_1[0] > list_1[1]:
    list_1[0], list_1[1] = list_1[1], list_1[0]

print("---")
# After swap
print(list_1)
print(list_1[0])
print(list_1[1])

The result looks like this:

[94, 36]
94
36
---
36
94

36 is now at index 0 and 94 is at index 1. If we ran this again nothing would happen as 36 is less than 96 so the if statement would be false. 94 bubble up above the lower 36. The reason for the bubble up instead of sink down is the focus is on the larger number moving up rather than the other value going down.

We’ll see this bubble effect when we look at a long list than 2. Let’s look at a list of 3. Again, this may seem like a very slow explanation but stick with it as it’s going to start to get more complicated as we have a list more than 2.

List 3 numbers

Let the list now be 94, 36, 5. Let’s put this in table to show the values and index

Lets apply the code we used for the 2 value list

If value at index 0 > value at index 0+1 is True then:
value at index 0 = value at index 0+1
value at index 0+1 = value at index 0
else (index 0 < index 0+1):
end

This will sort the first two value (index 0, index 0+1) 94 and 36. It’s easy to extend this to handle the third value as we can repeat the if statement.

If value at index 0 > value at index 0+1 is True then:
value at index 0 = value at index 0+1
value at index 0+1 = value at index 0
If value at index 0+1 > value at index 0+2 is True then:
value at index 0+1 = value at index 0+2
value at index 0+2 = value at index 0+1

The python for this is

list_2 =[94, 36, 5]
print (list_2)

if list_2[0] > list_2[1]:
    print("It is bigger - swap")
    list_2[0], list_2[1] = list_2[1], list_2[0]

if list_2[1] > list_2[2]:
    print("It is bigger - swap")
    list_2[1], list_2[2] = list_2[2], list_2[1]

print("---")
print(list_2)

The result looks like this:

[94, 36, 5]
---
[36, 5, 94]

94 has bubbled up two places. All good. Now we sorted the highest value to the top we need to run it again to sort out the 36 and the 5. This gives us a program to sort three numbers:

list_2 =[94, 36, 5]
print (list_2)

if list_2[0] > list_2[1]:
    list_2[0], list_2[1] = list_2[1], list_2[0]

if list_2[1] > list_2[2]:
    list_2[1], list_2[2] = list_2[2], list_2[1]

if list_2[0] > list_2[1]:
    list_2[0], list_2[1] = list_2[1], list_2[0]

print("---")
print(list_2)

The result looks like this:

[94, 36, 5]
---
[5, 36, 94]

Excellent – we can now sort a list of three numbers.

However, you may be starting to think a couple of things: 1) can we reuse the code that we have already written as we repeat the same thing twice? 2) how do we cope with a very long list of values – this won’t work with even 10 number. Is there a smarter way of doing this?

Yes! We need to look at this problem as a mathematical problem but don’t panic if maths is not your thing. Again taking things slowly is the key here (as we’re not great at maths to be very honest).

How many times will a number by sorted?

Our first problem with writing a lot of repeating code is knowing when to stop. We could (could) write a 100 if statements to swap values around and a) hope the list is less than a 100, b) hope the computer could cope with it, c) no one ever sees our code. For the bubble sort what is the maximum number of times that a value can be swapped (bubbled) with its neighbour? Let’s work it out.

So the maximum number of swaps needed to get a value from the bottom to the top is the length of the list -1. Easy. This is the number of times we would have to make sure that the highest value bubbled (swapped) to the top (right side) of the list.

Knowing how the maximum number of swaps for list is the first part of getting our algorithms to repeat, or loop, itself. We can now add a for loop (as we know how many times it will run) to our code so the code can be repeated until the condition is no longer true – in this case when the for loop runs out.

We can work out the list length by using a pre-defined algorithm or function that gives the length. In python this is the function len (shortened version of length) which we will use to give the length of the list defined as list_length. Knowing this we can use to set the number of times the loop will run to swap pairs of values to make larger values bubble up.

The for loop also gives us a helpful counter that is used to count the number of times the loop has run. At their simplest for loops are set with a maximum number of times they will loop. Every time they complete a loop the counter is increased by one starting at zero. This counting is the same for the index of the list so the value can be substituted allowing a direct reference to the list index on each loop.

As the loop counter is the same as the index we can substitute the for loop counter value for the index value of the list. We can test this by printing the values of the for loop counter and the index list. For loops we general define the counter as the letter i ‘eye’ . In the code below because we are writing letters the number has to be converted to a string through wrapping in the str function.

list_3 = [5,4,3,2,1]
list_length = len(list_3)
print(list_length) # 5
print("---")
for i in range (5):
    print("For loop counter value: " + str(i))
    print("List value at index same as loop counter: " + str(list_3[i]))

The result looks like this:

For loop counter value: 0
List value at index same as loop counter: 5
For loop counter value: 1
List value at index same as loop counter: 4
For loop counter value: 2
List value at index same as loop counter: 3
For loop counter value: 3
List value at index same as loop counter: 2
For loop counter value: 4
List value at index same as loop counter: 1

Now we know we can substitute the list index value for the loop value we can write the swapping condition and the swap as reference to the loop not the list index. This means the loop and the swap is linked so we can sort the first number from the list to the top. Here is the code for that along with a print of the loop counter to show you the value for each loop.

list_4= [5,4,3,2,1]
list_length = len(list_4)
print(list_4)
print("---")
for i in range(list_length - 1):
    print(i)
    if list_4[i] > list_4[i+1]:
        list_4[i], list_4[i+1] = list_4[i+1], list_4[i]
        print(list_4)
print("---")
print(list_4)

The result looks like this (the 5 has been bolded):

[5, 4, 3, 2, 1]
---
0
[4, 5, 3, 2, 1]
1
[4, 3, 5, 2, 1]
2
[4, 3, 2, 5, 1]
3
[4, 3, 2, 1, 5]
---
[4, 3, 2, 1, 5]

Awesome! We’ve now sorted the first number. But how do we do the other numbers? We could repeat the above code for the number of values in the list minus one as the last one will have been sorted if all the other ones are in place. To simply repeat the code for the second number isn’t that crazy an idea. For example if we run the above code for our list 5,4,3,2,1 after 4 rounds the list will be sorted

list_4= [5,4,3,2,1]
list_length = len(list_4)
print("---1")
print(list_4)
for i in range(list_length-1):
    if list_4[i] > list_4[i+1]:
        list_4[i], list_4[i+1] = list_4[i+1], list_4[i]
        print(list_4)

print("---2")
print(list_4)
for i in range(list_length-1):
    if list_4[i] > list_4[i+1]:
        list_4[i], list_4[i+1] = list_4[i+1], list_4[i]
        print(list_4)

print("---3")
print(list_4)
for i in range(list_length-1):
    if list_4[i] > list_4[i+1]:
        list_4[i], list_4[i+1] = list_4[i+1], list_4[i]
        print(list_4)

print("---4")
print(list_4)
for i in range(list_length-1):
    if list_4[i] > list_4[i+1]:
        list_4[i], list_4[i+1] = list_4[i+1], list_4[i]
        print(list_4)
print("---Final List")

print(list_4)

The results look like this

-START--1
[5, 4, 3, 2, 1]
[4, 5, 3, 2, 1]
[4, 3, 5, 2, 1]
[4, 3, 2, 5, 1]
[4, 3, 2, 1, 5]
---2
[4, 3, 2, 1, 5]
[3, 4, 2, 1, 5]
[3, 2, 4, 1, 5]
[3, 2, 1, 4, 5]
---3
[3, 2, 1, 4, 5]
[2, 3, 1, 4, 5]
[2, 1, 3, 4, 5]
---4
[2, 1, 3, 4, 5]
[1, 2, 3, 4, 5]
---Final List
[1, 2, 3, 4, 5]

This may seem like a barmy idea to just keep repeating the code but it’s another step to seeing how we could improve it. It’s better to get working inefficient code than keep trying fancy code that doesn’t work.

What we can see from the code above is we need another loop to go through all the positions in the list to check if a value is higher so it can bubble to the top. From the code above it took 4 loops to sort the 5 item list. The reason for 1 less than the total length is the last item does not need to sorted as it has sank to the bottom. This is not ideal as we will want to check the list has no swaps so an extra loop is good to use the length of the list. This makes sense if you had a list of 4 numbers you’d have to check the 4 positions to see if they needed swapping.

Putting this outer loop does t

list_5 =[9,8,7,6,5]
list_length2 = len(list_5)

print("--- Unsorted ---")
print(list_5)
print("---------------")

for i in range(list_length2):
    for j in range(list_length2 - 1):
        if list_5[j] > list_5[j+1]:
            list_5[j], list_5[j+1] = list_5[j+1], list_5[j]
            print(list_5)

print("--- Sorted ---")
print(list_5)
print("---------------")

The result looks like this …

--- Unsorted ---
[9, 8, 7, 6, 5]
---------------
[8, 9, 7, 6, 5]
[8, 7, 9, 6, 5]
[8, 7, 6, 9, 5]
[8, 7, 6, 5, 9]
[7, 8, 6, 5, 9]
[7, 6, 8, 5, 9]
[7, 6, 5, 8, 9]
[6, 7, 5, 8, 9]
[6, 5, 7, 8, 9]
[5, 6, 7, 8, 9]
--- Sorted ---
[5, 6, 7, 8, 9]
---------------

Wow! We have written an algorithm that sorted the list. Now, it won’t be the best way of doing this and there will be better, more sophisticated ways of doing this but the principle will be the same: iterate through the numbers horizontally looking for swaps starting at the first index location, once all swaps done then repeat starting at the next location in the list.

An algorithm that takes in a defined input and does one thing we can capture as a function. By capturing an algorithm as a function we can use is over and over. A quick introduction to functions:

def bubble_sort(list): # this is the name of the function and what it takes in
# for python the indentation is important to score the contents of the function
    list_length = len(list)

    print("--- Unsorted ---")
    print(list)
    print("---------------")
    for i in range(list_length):
        for j in range(list_length - 1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]
                print(list)
    print("--- Sorted ---")
    print(list)
    print("---------------")

# that's the end of the function. 

# Two list for the bubble_sort to work on
list = [6, 5, 4, 3, 2, 1, 0]
test_scores = [60, 85, 41, 30, 12, 95, 0]

# Feed the function. It doesn't matter what you call it as long as it's a list (or whatever the function can process

bubble_sort(list)
bubble_sort(test_scores)

The results work like above so we won’t show the results. Try it and you’ll see it how it works.