Home

 › 

Articles

 › 

What Is The Bubble Sort Algorithm, And How Does it Work? (With Examples)

bubble sort algorithm

What Is The Bubble Sort Algorithm, And How Does it Work? (With Examples)

The bubble sort algorithm is an example of a simple sorting algorithm. This type of algorithm arranges characters, strings, or numbers in a specific order determined by the problem you’re solving with your code.

A sort is often useful when you want to arrange items alphabetically or in numerical order. Sorting algorithms are a crucial part of programming, and the bubble sort is a favorite among students due to its simplicity. However, it isn’t the best choice if you need fast performance.

If you want to learn more about the bubble sort algorithm and how it works, you’re in the right place. Today’s article will break down how the bubble sort algorithm works and show you how to implement it. Let’s get into it!

What Is the Bubble Sort Algorithm?

Sorting algorithms give you a way to present data logically when you execute your code. When you’re learning to program, the bubble sort is one of the first algorithms you’ll learn because it allows you to visualize how a sorting algorithm works at a foundational level. 

The bubble sort algorithm is unique because it can only compare two adjacent sets of data. It moves through the entire array, dictionary, list, or string and compares each item, and sorts everything to your requirements.

The Algorithm

Before we explore how to create a bubble sort in your code, let’s look at how it works step by step:

  1. First, we would identify a collection of data that needs sorting. This can be a collection of numbers, words, or letters that you intend to arrange in a particular way. One common function of a bubble sort would be taking a list of numbers and ordering them by their value, either from lowest to highest or highest to lowest.
  2. The algorithm starts at the first item in a list, which would be the data at index 0. It compares that data to the data at index 1 to determine if a switch is necessary.
  3. If a switch is made, we have a flag that we set, which allows us to exit the algorithm to make it more efficient.
  4. Next, it compares index 1 to index 2, and it continues through the list until it reaches the end.
  5. Once the algorithm has gone through one time, it needs to go through the process again because it’s not finished until no switches need to be made. This is typically accomplished with nested loops that execute a bubble sort through the entire list until a conditional, operating on the flag, exits once we’ve gone through a full iteration with no changes.
  6. Once those nested loops have executed, the sorted list will be in the order intended so you can display it on the screen or use it for further operations in your code.
bubble sort algorithm
The Bubble sort algorithm is illustrated with a diagram.

Functioning of the Bubble Sort Algorithm

Now that we’ve covered the logic of the bubble sort algorithm, let’s dive deeper into an example. We’ll take a list of numbers that are out of order and let the bubble sort arrange them in ascending order.

To make it simple, we’ll use a list of four numbers:

29, 15, 0, -5

The first calculation the bubble sort would do would be to check the values of index 0 and index 1 as we discussed above. Since 29 is bigger than 15, their positions will switch, giving us this sequence of numbers:

15, 29, 0, -5

Next, the algorithm compares 29 and 0. Here is the resulting list:

15, 0, 29, -5

The last time through this first iteration, the algorithm compares 29 to -5, giving us this list:

15, 0, -5, 29

Our list isn’t quite where we need it to be, and the next iteration will help us sort through that. We will see the list change in this way:

0, 15, -5, 29

0, -5, 15, 29

0, -5, 15, 29

0, -5, 15, 29

Then the third iteration would give us this result:

-5, 0, 15, 29

-5, 0, 15, 29

-5, 0, 15, 29

-5, 0, 15, 29

Now, because the list is fully sorted, we will need a way to tell the loop to stop executing. This is to make it more efficient. To do that, we typically use a boolean variable along with some conditional statements to allow the algorithm to break out of the loop once no switches have been made.

Implementation of the Bubble Sort Algorithm Using a For Loop

Now, let’s throw some code for the bubble sort algorithm into Python to get a good understanding of how it works as a sorting method. Here is how we would implement it with a for loop:

def bubbleSort (numArray, z):
	for a in range(z-1):
		swap = False
		for b in range (0, z-a-1):
			if numArray[b] > numArray[b+1]:
				swap = True
				numArray[b], numArray[b+1] = numArray[b+1], numArray[b]
		if not swap:
			return numArray


numberArray = [82, 67, 0, -500, -80, 99, 2]
x = len(numberArray)
print (“Sorted Array:”)
print (bubbleSort(numberArray, x))

Explanation of the Code

Let’s break this code down step-by-step so we can understand what’s going on.

Initializing the Array

First, we need to initialize our array with a set of numbers we’d like to sort (numberArray). These are deliberately initialized in random order to demonstrate how the bubble sort algorithm works. Next, we initialize a variable that hosts the count of items we have in the array (x). We’ll use this variable later to control how many times we iterate through the loop.

Defining the Bubble Sort Algorithm

Two values are passed into the algorithm, which is defined as bubbleSort. The first value is the array itself. Then we also pass in the length of the array. Inside the algorithm, those are reassigned as numArray and z, respectively.

The loop we use to execute the bubble sort will iterate through a certain number of times, but it’s not always necessary for it to run its course. So, we must first set up a boolean variable at the beginning of the outer for loop that will change from False to True in the inner loop if a swap is made during our sorting algorithm.

As we talked about earlier, a bubble sort algorithm compares two adjacent values to determine if the array needs to be changed. So, we set up a conditional to determine which value is the highest. If the value of the first variable is higher, it will switch places with the adjacent item in the array. And, since a swap has been made, we will also set the boolean value (swap) to True so we don’t break out of the loop just yet.

Once the inner loop has gone through the array the first time, the boolean value will be set to True, so we go into the external loop the second time, setting the boolean (swap) to False again to start the process all over. This boolean must be re-initialized each time because we want our algorithm to be able to exit the first time we go through the inner loop once without a swap. You can go through the entire process without an exit condition, but your program will execute faster with it implemented.

Visiting the Ranges

The bubble sort algorithm will continue this process until we’ve gone through one full iteration of the internal loop without making a swap. In the for loop syntax, the range tells the loop when to start, stop, and how many steps to increment. It can take three parameters, but it only needs one—at what point the for loop should stop.

In our external for loop, we only need to tell it where to stop, which is at the very last index of the array. We have to use z-1 as the range there because the index starts numbering at 0 rather than 1. So, if we left at z, it would go one more time than we needed.

In our internal for loop, we have two parameters because we want to tell it where to start—at the first index, 0—and where to stop. We stop a little sooner than the external for loop because we don’t need to check those remaining items in the array.

Updating the Array

The if statement creates a condition to determine if the two adjacent items in the array need to switch their positions. Since we’re sorting the numbers in ascending order, if the first number is bigger than the second number compared, then that first number needs to move one place to the right, which means the second number needs to move one place to the left since it’s smaller. 

This switch can happen a few different ways, but the quickest and easiest way to do this is to assign the values to the adjacent items at the same time. This is accomplished with the following statement: numArray[b], numArray[b+1] = numArray[b+1], numArray[b]. An alternative method would be to create a temporary variable to hold one of the values that need to move while the other moves over with a simple assignment. But, since this requires more code, it’s much more efficient to accomplish when we assign them both at the same time.

Output of Results

When the bubble sort method breaks out of the nested for loops and returns to the main program, it sends the resulting array to the print statement we called the method from and displays the results on the screen, giving us an array with seven items sorted in ascending order by number value.

The sorted array we would get back from our example:
[-500, -80, 0, 2, 67, 82, 99]

Best and Worst Use Cases of the Bubble Sort Algorithm

The bubble sort algorithm works efficiently when we have a limited number of data items we need to arrange in a certain order. When you scale up or add too many data points, bubble sort starts to struggle. If you need a more efficient algorithm, there are plenty of options. You can look to merge sort and quick sort, both of which are significantly faster.

Let’s look at the time and space complexity to get an idea of performance.

Time Complexity of the Bubble Sort Algorithm

CaseTime Complexity
Best0 (N)
Average0 (N^2)
Worst0 (N^2)

(N represents the number of items in the data set.)

The best case exists when the array is already sorted and does not need to make any changes. However, before the sorting algorithm begins, the program doesn’t know this, so it must go through the steps to sort the array at least one time. 

This isn’t typical when dealing with data that you need to sort. Often, we’re working with data entered by a user or pulled from another method executed by the program. And it’s not the most efficient way to design a program that requires the user to enter data alphabetically or numerically.

Space Complexity of the Bubble Sort Algorithm

CaseSpace Complexity
BestO(1)
AverageO(1)
WorstO(1)

The bubble sort algorithm doesn’t have a huge need for space. Because, at most, we’re only adding in a boolean to check for swaps and temporary variables to hold data while we’re swapping if necessary. For this reason, the space complexity doesn’t change when we’re using larger sets of data.

Wrapping Up

The bubble sort algorithm can be efficient when you only want to sort small amounts of data. But it really isn’t the most efficient, and it isn’t ideal due to its performance. Instead, it is most useful as a learning tool for beginning programmers to learn how the computer executes algorithms. If you are taking a data structures and algorithms course, you will have to master this one. Once you grasp the basics of sorting algorithms, you can graduate to more efficient ones.

Frequently Asked Questions

What is the bubble sort algorithm?

A bubble sort algorithm is a simple sorting algorithm that compares two adjacent values and makes a switch based on a condition set up in our code. It typically uses either a while loop or a for loop to iterate through each set of adjacent items until it reaches the end of the data set. However, it requires more than one iteration of the full data set to sort the data in ascending or descending order.

What are the limitations of the bubble sort algorithm?

When we have large sets of data, the bubble sort algorithm is not the best use of our computer power. Other sorting algorithms would be better choices because they likely won’t take as much time to execute the algorithm.

 

What is the time complexity of the bubble sort algorithm?

The time complexity ranges from 0 (N) to 0 (N^2), where the best-case scenario exists when the data set is already sorted. N represents the number of items in the data set, so the time complexity can increase a great deal when working with large collections of data.

What is the space complexity of the bubble sort algorithm?

The space complexity, no matter how big our data set, is O(1), which means it remains the same. In theory, if you had a data set of 200 items, it would take the same amount of space as one with 100.

When should the bubble sort algorithm be used?

Because it is most effective with small data sets, the bubble sort algorithm is most useful in educational settings, when beginning programmers are first learning how to code sorting algorithms.

What are the different ways to implement the bubble sort algorithm?

Because we need to iterate through the entire data set to execute a bubble sort algorithm, it is typically implemented with loops—either a for loop or a while loop.

What are the alternatives to the bubble sort algorithm?

There are several algorithms we can use to perform a sort. The following are some of the most commonly used sorting methods: selection sort, insertion sort, bucket sort, heap sort, and merge sort.

To top