Skip main navigation

An introduction to Bubble Sorts

How does a bubble sort work? Watch James Robinson explain.
3.4
In this step, we’re going to look at a method of sorting lists called the Bubble Sort. The Bubble Sort algorithm is one of the simplest sorting algorithms to implement. However, it’s poor efficiency means that it’s more often used as a teaching tool to introduce the concept of sorting rather than an algorithm that’s actually used in practise. This means that virtually every student of computer science will, at some point or another, learn how the Bubble Sort works. Let’s look at the Bubble Sort algorithm in the real world. Imagine there are five cars, all travelling down a straight road. The cars are all being driven on cruise control but each at a different speed.
42.2
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 occurring, with the cars switching positions with any slower car in front of them. Eventually, the cars will sort themselves according to their speeds, with the fastest car being at the front of the queue and the slowest at the back. This is similar to how the Bubble Sort algorithm works. Let’s take a look.
69.8
In the following example, we’ll use the Bubble Sort to organise a variety of balls used in some different sports, according to their size. We’ll start with the balls in a random order, lined up in a horizontal line. We’ll use a variable called Swapped to track whether we’ve swapped any balls as we go. As yet, we’ve not changed any balls around. So we’ll set Swapped to False. Then we compare the first two balls in the line.
99.4
We can see that the tennis ball is smaller than the soccer ball, so there’s no need to swap their positions. Our swap variable remains false. Next, we compare the soccer ball with the pool ball. The soccer ball is larger than the pool ball, so we need to swap their positions.
120.9
Because we’ve made this change, we’ll also need to make sure that Swapped is set to True. Next, we compare the soccer ball with the basketball. They’re the right way around. We don’t need to swap them. We keep progressing down the line, swapping balls if needed.
141
Once we’re at the end, we can check the Swapped flag. If it’s true, we need to go back and look at all the balls again.
161.4
As you can see, repeated repetitions of the algorithm result in the balls all being sorted. Eventually, once all the balls are in order, the arm will go down the row, measure each ball, but not need to swap any. At this point, Swapped remains False. And the loop can come to an end.
184.6
So to summarise, the Bubble Sort algorithm begins by setting Swap to False, checks each pair of items in the set comparing their size. If the one on the left is greater than the one on the right, the balls are swapped. If not, they’re ignored. At the end of the set, if a swap has occurred, Swapped is reset to False. And the set is examined once again. Once the robot arm gets to the end without making any swaps, then it knows that the set is sorted. In the next step, we’ll look at implementing this in Python.

In this step, we’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 we’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, we 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.

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

Six unsorted balls in a line, with a robotic claw with a screen above them. In order from left to right, the balls are a tennis ball, a soccer ball, a pool ball, a basketball, a golf ball and a bowling ball.

  1. We can start by setting a variable that states we’ve changed the order of the list. As the list is jumbled (or might be), we set swapped = True.
  2. Now, we want to keep repeating our sorting actions, until we find we haven’t made any changes to the order of the balls since the last time through. This is because if we’ve looked at all the balls’ positions and have made no changes, the balls must be sorted.
  3. As we’ve yet to change the order of any balls, we’ll set swapped to False. Then we can compare the first two balls in the line.
  4. We can see that the tennis ball is smaller than the soccer ball, so there is no need to change their positions.

    <img src="https://s3-eu-west-1.amazonaws.com/rpf-futurelearn/programming-102/bubblesort/102-2.3-bubble-sort-first-comparison.png" alt="Six unsorted balls in a line In order from left to right, the balls are a tennis ball, a soccer ball, a pool ball, a basketball, a golf ball and a bowling ball. A purple bracket underneath the balls contains just the tennis and soccer balls. A robotic claw is measuring the width of the soccer ball. A screen on the claw reads "63

  5. swapped remains False as no changes to the order have been made.
  6. Next we compare the soccer ball with the pool ball. The soccer ball is larger than the pool ball, so we can swap their positions.

    A line of five balls with a gap after the second one. To the left of the gap are a tennis ball and a soccer ball. A robotic claw has picked up a pool ball from the third position in the line and is moving it to where the soccer ball is in the line. After the gap are a basketball, a golf ball and a bowling ball. A screen on the claw reads "SWAP" and a purple bracket underneath the balls highlights the second and third positions in the line (the soccer ball and the gap).

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

    Six balls in a line In order from left to right, the balls are a tennis ball, a pool ball, a soccer ball, a basketball, a golf ball and a bowling ball. A purple bracket underneath the balls contains just the pool and soccer balls. A robotic claw is above the soccer ball. A screen on the claw reads "swapped = True".

  8. Now we compare the soccer ball with the basketball. The basketball is larger, so again, we don’t need to swap them.
  9. We keep progressing down the line, swapping the balls if needed.
  10. Once we’re at the end, we can check the swapped flag. As we have made a change to the order, we will find it is True, so we need to go back to step 2.

    Six balls in a line In order from left to right, the balls are a tennis ball, a pool ball, a soccer ball, a golf ball, a bowling ball and a basketball. A purple bracket underneath the balls contains just the bowling ball and basketball. A robotic claw is above the basketball. A screen on the claw reads "swapped = True".

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

Six balls in a line ordered by size. From left to right the balls are a golf ball, a pool ball, a tennis ball, a bowling ball, a soccer ball and a basketball. Above the basketball is a robotic claw, which has a screen reading "swapped = False".

What other analogies, scenarios or activities could you use to explain the bubble sort to your learners? Use the comments section to share your thoughts.

This article is from the free online

Programming 102: Think Like a Computer Scientist

Created by
FutureLearn - Learning For Life

Our purpose is to transform access to education.

We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.

We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.

Learn more about how FutureLearn is transforming access to education