3.3.mp4

An introduction to Bubble Sorts

In this step, you’re going to look at a method of sorting lists called bubble sort.

The bubble sort algorithm is one of the simplest sorting algorithms to implement. It’s not a very widely used sorting algorithm, but is more often used as a teaching tool to introduce the concept of sorting. This means that virtually every student of computer science will, at some point or another, learn how bubble sort works.

In this step I’ll take a broad look at the bubble sort algorithm, try to explain how it works, and provide a visualisation of the algorithm in action. Later on you’ll learn why it is not the best algorithm to sort a million 32-bit integers.

Real-world examples of the bubble sort algorithm are hard to find. However, with a little imagination, you can see how a bubble sort might happen in a real situation.

Imagine there are five cars all travelling down a straight road. They are all being driven on cruise control, but each of the cars’ speeds have been set to slightly different values.

When a car is travelling faster than the car in front, it will overtake it, and occupy the slower car’s position in the traffic. This will keep happening, with each car switching positions with any slower car in front of it. Eventually the cars will sort themselves according to their speeds, with the fastest car being at the front of the queue of traffic.

This is in essence how bubble sort works.

I am going to look in a little more detail at what is going on with the algorithm when I use it to sort some data. In the following example, I will sort some different balls, used in a variety of sports, according to their size. I’ll start with the balls in a random order, lined up in a horizontal line.

1. I start by setting a variable that states whether I’ve changed the order of the list or not. As the list is jumbled (or might be), I set swapped = True.

2. Now, I want to keep repeating the sorting actions, until I find I haven’t made any changes to the order of the balls since the last time through. This is because if I’ve looked at all the balls’ positions and have made no changes, the balls must be sorted.

3. As I’ve yet to change the order of any balls, I set swapped to False. Then I can compare the first two balls in the line.

4. I see that the tennis ball is smaller than the soccer ball, so there is no need to change their positions.

5. swapped remains False as no changes to the order have been made.

6. Next I compare the soccer ball with the pool ball. The soccer ball is larger than the pool ball, so I can swap their positions.

7. Because I’ve made a change to the order of the balls, I need to make sure that swapped = True.

8. Now I compare the soccer ball with the basketball. The basketball is larger, so again, I don’t need to swap them.

9. I keep progressing down the line, swapping the balls if needed.

10. Once I’m at the end, I can check the swapped flag. As I have made a change to the order, I find it is True, so I need to go back to step 2.

As you can see, repeated iterations within the algorithm result in the balls all being sorted, and I know this is the case when swapped = False and I no longer have to repeat the instructions.

<- previous

next ->