Learn All About Bubble Sort Algorithm (With Code Examples)

10 mins read

Sorting algorithms play a crucial role in organizing data efficiently, and Bubble Sort is one of the simplest techniques to achieve this. It repeatedly compares adjacent elements and swaps them if they are in the wrong order, making it a straightforward yet fundamental sorting method. While not the most efficient for large datasets, Bubble Sort is widely used for teaching purposes due to its easy-to-understand nature.

In this article, we will explore the working principle of Bubble Sort, analyze its time complexity, and discuss its advantages and limitations with an implementation in C++ and Python.

Understanding Bubble Sort Algorithm

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is completely sorted. It is called Bubble Sort because the larger elements "bubble up" to the end of the list with each pass.

How Bubble Sort Works?

1. Start from the first element.
2. Compare it with the next element.
3. If the first element is greater than the second, swap them.
4. Move to the next pair and repeat the process.
5. The largest element moves to the last position in each pass.
6. Repeat the process for the remaining elements until the whole list is sorted.

Real-Life Example: Arranging Books by Height

Imagine a librarian wants to arrange books on a shelf in increasing order of height.

• The librarian picks the first two books and compares their heights.
• If the first book is taller than the second, they swap them.
• Then, they move to the next pair and continue swapping until the tallest book reaches the end.
• They repeat the process for the remaining books until all are sorted.

This mimics how Bubble Sort moves larger numbers to the right while sorting the rest of the list.

Bubble Sort Algorithm

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.

Algorithm For Bubble Sort

1. Start
2. Repeat the following steps for (n-1) passes:
• Iterate from the first element to the second last element.
• Compare adjacent elements.
• Swap them if they are in the wrong order (i.e., if the left element is greater than the right one).
• Continue the process until the largest element reaches the correct position at the end.
3. Continue the process for the remaining (n-1) elements.
4. Stop when no more swaps are needed.
5. End

Pseudocode For Bubble Sort

BubbleSort(arr, n)
for i = 0 to n-1
     for j = 0 to n-i-2
         if arr[j] > arr[j+1] then
             swap(arr[j], arr[j+1])
     end for
 end for
 return arr

Example:

Let's say we have an array:
arr[] = {5, 3, 8, 4, 2}

Pass 1 (Sorting the largest element to the last)

• Compare 5 & 3 → Swap → [3, 5, 8, 4, 2]
• Compare 5 & 8 → No Swap → [3, 5, 8, 4, 2]
• Compare 8 & 4 → Swap → [3, 5, 4, 8, 2]
• Compare 8 & 2 → Swap → [3, 5, 4, 2, 8]

(Largest element 8 is now at the correct position)

Pass 2

• Compare 3 & 5 → No Swap → [3, 5, 4, 2, 8]
• Compare 5 & 4 → Swap → [3, 4, 5, 2, 8]
• Compare 5 & 2 → Swap → [3, 4, 2, 5, 8]

Pass 3

• Compare 3 & 4 → No Swap → [3, 4, 2, 5, 8]
• Compare 4 & 2 → Swap → [3, 2, 4, 5, 8]

Pass 4

• Compare 3 & 2 → Swap → [2, 3, 4, 5, 8]

The array is now sorted!

Implementation Of Bubble Sort In C++

Here’s a C++ program that implements Bubble Sort and prints the sorted array.

Code Example:

#include <iostream>
using namespace std;

// Function to implement Bubble Sort
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false; // Optimization: To check if any swap happens
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        // If no elements were swapped, break early
        if (!swapped) break;
    }
}

// Function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    bubbleSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output: 

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 

Explanation: 

In the above code example-

1. We start by including the <iostream> library to handle input and output operations.
2. Now we use namespace std; to avoid prefixing standard library elements with std::.
3. The bubbleSort() function implements the Bubble Sort algorithm to sort an array in ascending order.
4. We use two nested loops:
• The outer loop iterates through the array, controlling the number of passes.
• The inner loop compares adjacent elements and swaps them if they are in the wrong order.
5. We introduce a swapped flag to optimize the sorting process:
• If no swaps occur in a pass, it means the array is already sorted, so we break out of the loop early.
6. The printArray() function iterates through the array and prints its elements.
7. In main(), we define an integer array with some unsorted values.
8. We calculate the number of elements in the array using sizeof(arr) / sizeof(arr[0]).
9. We print the original array using the printArray() function.
10. We call the bubbleSort() function to sort the array.
11. We print the sorted array to verify the output.
12. The program returns 0, indicating successful execution.

Time And Space Complexity Analysis Of Bubble Sort Algorithm

Bubble Sort is a simple sorting algorithm, but its efficiency depends on the arrangement of elements in the input array.

1. Time Complexity Analysis

Worst Case (O(n²)) - Reverse Sorted Order

• In the worst-case scenario, the array is sorted in descending order.
• Each element is compared with every other element.
• The total number of comparisons: (n−1)+(n−2)+...+2+1 = n(n−1)/2 ≈ O(n²)
• Example:
  Input:{9, 8, 7, 6, 5}
  Comparisons: Maximum required.

Best Case (O(n)) - Already Sorted Array

• If the array is already sorted, no swaps are needed.
• The algorithm makes one full pass to verify sorting.
• If an optimized Bubble Sort with a swapped flag is used, it exits early after one pass.
• The time complexity is: O(n)
• Example:
  Input: {1, 2, 3, 4, 5}
  Comparisons: n-1, and the loop breaks early.

Average Case (O(n²)) - Random Order

• In an average scenario, the array elements are randomly arranged.
• The total comparisons are still approximately: O(n²)
• Example:
  Input: {5, 1, 4, 2, 8}
  Comparisons: Intermediate number of swaps.

2. Space Complexity Analysis

Space Complexity: O(1)

• Bubble Sort is an in-place sorting algorithm, meaning:
• It does not use any extra space.
• Swaps occur within the array itself.
• The only extra space used is for temporary variables (i, j, and swapped flag).

Advantages Of Bubble Sort Algorithm

Some of the advantages are as follows:

• Simple and Easy to Implement → Straightforward logic, easy to code.
• In-Place Sorting (O(1) Space Complexity) → Does not require extra memory.
• Stable Sorting Algorithm → Preserves the order of equal elements.
• Best Case Performance O(n) (With Optimization) → Exits early if the array is already sorted.

Disadvantages Of Bubble Sort Algorithm

Some of the disadvantages are as follows: 

• Slow for Large Data Sets (O(n²) Time Complexity) → Inefficient compared to other sorting algorithms.
• Too Many Swaps → Unnecessary swaps increase execution time.
• Not Used in Real-World Applications → Better alternatives exist (QuickSort, MergeSort).
• Inefficient for Nearly Sorted Arrays (Without Optimization) → Performs redundant passes if not optimized.

Applications of Bubble Sort Algorithms

While Bubble Sort is not the most efficient sorting algorithm for large datasets, it still has some practical applications in specific scenarios due to its simplicity and ease of understanding. Here are some of the key applications of Bubble Sort:

1. Educational Tool For Teaching Sorting Algorithms

Bubble Sort is widely used in introductory computer science courses to teach the basic concepts of sorting algorithms. Its simple logic helps students understand how comparison-based sorting works, with an emphasis on element swapping and iterative processing.

2. Small Datasets Or Nearly Sorted Data

For small datasets, the overhead of more complex algorithms may not justify their use, and Bubble Sort’s simplicity can be a good choice. If the data is nearly sorted (i.e., only a few swaps are needed), Bubble Sort can perform well and be more efficient than other algorithms due to its early stopping mechanism (when no swaps occur in a pass).

3. Sorting With Minimal Space Requirements

Bubble Sort is an in-place sorting algorithm, meaning it does not require extra memory (beyond a few variables for the loop). This makes it useful in situations where memory constraints are significant, and using additional memory for other sorting algorithms might not be feasible.

4. Stable Sorting Requirement

Bubble Sort is a stable sorting algorithm, which means that it preserves the relative order of equal elements in the dataset. This property can be valuable in cases where stability is required, such as when sorting objects based on multiple fields (e.g., sorting students by grade, but preserving their original order if they have the same grade).

5. External Sorting (In Limited Scenarios)

In very small-scale external sorting scenarios (like sorting data that cannot fit entirely in memory), Bubble Sort can sometimes be used where simplicity and low memory usage are more important than performance.

6. Simple Data Set Operations

When working with simple data structures like arrays or lists, especially in situations where the dataset is already mostly sorted or the number of elements is very small, Bubble Sort can be applied to achieve quick results without needing complex setups.

7. Comparing Algorithms In Benchmarking

Bubble Sort is often used in algorithmic benchmarking as a baseline comparison. Its poor performance against more sophisticated algorithms like Quick Sort or Merge Sort makes it an easy point of reference to demonstrate the importance of algorithm optimization.

Conclusion

Bubble Sort is a simple, comparison-based sorting algorithm that works by repeatedly swapping adjacent elements until the entire list is sorted. While it’s not the most efficient algorithm for large datasets due to its O(n²) time complexity, it serves as an excellent tool for educational purposes, helping beginners understand the fundamental concepts of sorting.

We also explored how the algorithm works, its time complexity analysis, and the possibility of optimization through early stopping. Though it is rarely used in production environments due to its inefficiency, Bubble Sort can be useful for small datasets, nearly sorted data, or situations with minimal memory requirements.

Ultimately, while more efficient sorting algorithms like Quick Sort and Merge Sort should be preferred for large-scale data, Bubble Sort remains a valuable learning tool and can still serve practical purposes in specific, simple applications.

Frequently Asked Questions

Q. What is Bubble Sort?

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Q. How does Bubble Sort work?

In each pass through the list, Bubble Sort compares adjacent elements and swaps them if needed. The largest unsorted element "bubbles" up to its correct position at the end of the list. This process continues for each element until the entire list is sorted.

Q. What is the time complexity of Bubble Sort?

The time complexity of Bubble Sort is O(n²) in the worst and average cases, where n is the number of elements in the array. In the best case (when the array is already sorted), the time complexity can be O(n) if an optimized version with early stopping is used.

Q. What are the advantages of using Bubble Sort?

• Simple to implement and understand.
• Stable sorting algorithm, preserving the relative order of equal elements.
• Efficient for small datasets or nearly sorted data.
• In-place sorting: doesn’t require additional memory.

Q. What are the disadvantages of Bubble Sort?

• Inefficient for large datasets due to its O(n²) time complexity.
• Compared to more advanced sorting algorithms (like Quick Sort or Merge Sort), it is significantly slower for large or unsorted data.

Q. When should Bubble Sort be used?

Bubble Sort should be used when:

• The dataset is small or nearly sorted.
• Memory usage is a concern, as it is an in-place algorithm.
• Teaching or learning basic sorting techniques in educational environments.

Suggested Reads: 

1. Difference Between Hashing And Encryption Decoded
2. 53 Frequently Asked Linked List Interview Questions With Answers 2024
3. Data Structure Interview Questions For 2024 [With Detailed Answers]
4. Tree Topology | Advantages & Disadvantages In Computer Network
5. Decoding Data Redundancy In DBMS| Causes, Advantages, Solutions