Getting ready for your next technical interview? As a software developer, you know how important it is to brush up on your sorting algorithms — they’re a frequent feature in coding interviews!
In this article, we’ll help you review the bubble sort algorithm by covering all the basics:
- What Is Bubble Sort?
- How the Bubble Sort Algorithm Works
- Bubble Sort Pseudocode
- Bubble Sort Code With Example
- Bubble Sort Complexity
- Advantages of Bubble Sort
- Disadvantages of Bubble Sort
- Bubble Sort FAQs
What Is Bubble Sort?
The bubble sort algorithm sorts a given set of elements in a particular order by continually swapping two consecutive elements that are not in the required order.
It’s a comparison-based sorting algorithm that sorts a set of elements by making several passes over the array and swapping adjacent elements that are not in the required order (ascending or descending).
Bubble sort is simple — it is often used to introduce the concept of sorting. It is most useful when the list of elements is almost sorted. It can detect a minute error in an almost sorted array and fix it with linear complexity — we’ll talk more about this later!
First, let’s look at how it works first.
How the Bubble Sort Algorithm Works
We already know that bubble sort works in passes. So, let’s look at the first pass:
- Initially, we consider the first and second elements and compare them. If they are in the correct order, we leave them as they are and move forward. Otherwise, we swap them to be in the right order, and then we move forward.
- Then we consider the second and third elements and compare them. If they are in the correct order, we leave them as they are and move forward. Otherwise, we swap them to be in the correct order, and then we move forward.
- We do this until the last two elements are compared.
This completes one pass of bubble sort. We can be sure that after the first pass, the element in the last place, which has to be the largest number of the array, is correctly placed.
Let’s move to the second pass:
- We will repeat what we did in the first pass: Starting from the first element, check adjacent elements and place them in the correct order.
- We know that the last element is correctly placed, so we will not compare the last and second-last elements.
After the second pass, we can be sure that the element at the second-last position is in the correct position.
After every pass, at least one element from the unsorted part of the array gets placed at its correct position. We need to make a total of n – 1 passes, where n is the size of our array, to get our array sorted.
Bubble Sort Pseudocode
Bubble sort is a simple algorithm — the pseudocode for it is also pretty simple and short.
Have a look and use it to write your code in a programming language of your choice.
bubbleSort(array, size)
for i ← 0 to size - 2
for j ← 0 to size - 2 - i
If array[j] and array[j + 1] are not in the correct order
Swap array[j] with array[j + 1]
Bubble Sort Code With Example
We’re using C++ to demonstrate how bubble sort works. You can do this in C, Java, Python, or any programming language you like.
// Bubble sort in C++
#include
using namespace std;
// Function to sort an array using bubble sort
void bubbleSort(int arr[], int size)
{
// The outer loop is to make a total of size - 1 pass
// [(size - 2) - (0) + 1 = size - 1]
for (int i = 0; i <= size="" -="" 2;="" i++)="" {="" the="" inner="" loop compares="" adjacent="" elements="" and="" swaps="" them="" if="" they="" are="" in="" wrong="" order.="" we="" can="" also="" say="" that="" it="" chooses="" an="" appropriate="" element="" from="" unsorted="" part="" put="" sorted="" for="" (int="" j="0;" <="size" i="" j++)="" (="" arr[j]=""> arr[j + 1])
{
swap(arr[j], arr[j + 1]);
}
}
}
}
// function to print the array
void showArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << array[i] << " ";
}
cout << "n";
}
// driver code
int main() {
int arr[] = { 2, 1, 5, 4, 3};
int len = sizeof(arr) / sizeof(arr[0]);
cout << "Array before sorting:n";
showArray(arr, len);
bubbleSort(arr, len);
cout << "Sorted array in ascending order:n";
showArray(arr, len);
}
Output:
Array before sorting:
2 1 5 4 3
Sorted array in ascending order:
1 2 3 4 5
Bubble Sort Example
arr = [2, 1, 5, 4, 3]
1st pass:
We compare the first two elements arr[0] and arr[1]. We see that arr[0] > arr[1], which is not the order we want. So, we will swap them and move forward.
Then, we compare arr[1] and arr[2]. As they are in the correct order, we don’t swap them.
Next come arr[2] and arr[3]. They are not in the correct order, so we swap them.
Then we compare arr[3] and arr[4]. They are also not in the correct order — swap!
This completes the first pass of bubble sort. “5” is now in the correct position.
2nd pass:
We repeat what we did before — first, we compare arr[0] and arr[1]. They are in the correct order, so we leave them as is.
Next, we compare arr[1] and arr[2]. They are also in the correct order.
We move to arr[2] and arr[3]. They are not in the correct order, so we swap them.
Remember: In this pass, we don’t need to compare arr[3] with arr[4], as we know that arr[4] is already sorted.
The array is sorted, but bubbleSort will make two more passes before giving you the final output:
Bubble Sort Code Optimization
In the algorithm section, we said that we need n-1 passes to sort an array of size n.
However, sometimes, the array gets sorted before completing all n-1 passes (as seen in the example above).
In some cases, the array might get sorted in just one pass! For example, array A = {1, 2, 3, 4, 5, 6, 8, 7}. But the code above will still make n – 1 = 7 passes.
How can we use this information to optimize our code?
After each pass, we’ll need to check if the array is sorted — if we made no swaps in that pass, it means that all the elements are correctly placed and hence sorted.
We’ll use a boolean variable flag, marked “true” at the beginning of a pass. If we make any swaps in the current pass, flag will be marked “false.” If the flag’s value is true at the end of a pass, the array is sorted, and we will not make any additional passes.
Here’s the optimized code:
// Bubble sort in C++
#include
using namespace std;
void bubbleSort(int arr[], int size)
{
for (int i = 0; i < size; i++)
{
bool isSorted = true;
for (int j = 0; j < size - i - 1; j++) { if ( arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
isSorted = false;
}
}
if ( isSorted )
{
break;
}
}
}
void showArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
cout << array[i] << ' ';
}
cout << 'n';
}
// driver code
int main() {
int arr[] = { 2, 1, 5, 4, 3};
int len = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, len);
cout << "Sorted Array in Ascending Order:n";
showArray(arr, len);
}
Bubble Sort Complexities
Space Complexity
The space complexity for the bubble sort algorithm is O(1), as it does not need any extra space to perform the sorting operation.
Time Complexity
- Best Case: O(n)
This occurs when we have an already sorted array. We make one pass to verify if the array is sorted.
- Average and Worst Case: O(n2)
For the first pass, the inner for loop runs n – 1 times
For the second pass, it runs n – 2 times
For the ith pass, the inner loop runs n – i times.
In total, it runs for (n – 1) + (n – 2) + … + 2 + 1 times, which is of the order O(n2). Its worst-case complexity is also O(n2). It occurs when the given array is sorted in descending order.
Advantages of Bubble Sort
- Is simple to write and easy to understand
- Takes a few lines of code
- Sorts data in place; requires very little additional memory
Disadvantages of Bubble Sort
- Average time increases quadratically with the number of elements
- Not suitable for a large amount of data
Bubble Sort FAQs
Question 1: Is bubble sort a stable sort?
Answer: First, let’s understand what a stable sort is. When two elements are of equal value, a stable sorting algorithm preserves the elements’ relative order — the element’s relative position in the output will be the same as in the input. The bubble sort algorithm is stable, as it does not swap elements that have the same value.
Question 2: Is bubble sort an in-place sorting algorithm?
Answer: An algorithm is called in-place when it only needs a constant amount of extra space to produce the desired output. We know that the bubble sort algorithm’s space complexity is O(1). Therefore, bubble sort is an in-place sorting algorithm.
Question 3: Why is bubble sort called so?
Answer: With each pass in bubble sort, adjacent elements that are not in the correct order get swapped. Basically, elements greater than their adjacent elements “bubble up” or move towards their proper position with each pass. Hence the name “bubble” sort.
Are You Ready to Nail Your Next Coding Interview?
Sorting algorithms interview questions feature in almost every coding interview for software developers. If you’re looking for guidance and help to nail these questions and more, sign up for our free webinar.
As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!
Sign up now!
———-
Article contributed by Divyansh Gupta
