Bubble Sort Algorithm

Last updated on July 13th, 2024 at 10:46 am

We will discuss the Bubble Sort Algorithm, pseudo code, Code implementation of bubble sort in C, C++, Java, JavaScript, Python, advantages & disadvantages, and time & space complexity of Bubble sort.

1. What is Bubble Sort Algorithm?

Bubble Sort Algorithm is a comparison-based algorithm.

Bubble Sort compares each element in the list with the next element. Elements are swapped if required. In every pass, one element comes to its position. This process repeats until a pass is made without disturbing any elements from their position.

Bubble Sort is simple but having high time complexity

1.1 Example for Bubble Sort

Sort the given elements (7, 5, 2, 4, 3 and 9) by using bubble sort.
After the first pass, we get
7, 5, 2, 4, 3, 9
5, 7, 2, 4, 3, 9
5, 2, 7, 4, 3, 9
5, 2, 4, 7, 3, 9
5, 2, 4, 3, 7, 9

After the first pass, the first largest element (9) is on the 

top of array. So we have
5, 2, 4, 3, 7, 9

After the second pass, we get
2, 4, 3, 5, 7, 9

After the third pass, we get
2, 3, 4, 5, 7, 9

After the fourth pass, we get
2, 3, 4, 5, 7, 9

After the fifth pass, we get
2, 3, 4, 5, 7, 9

The sorted list is 2, 3, 4, 5, 7, 9

2. Pseudo Code of Bubble Sort

BUBBLE_SORT(A)
1. for i <- 1 to n-1
2. for j <- 1 to n-1
3. If(A(j) > A(J+1))
4. Temp = A(j)
5. A(j) = A(j+1)
6. A(j+1) = Temp

3. Code Implementation of Bubble Sort

3.1 Bubble Sort in C

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {7, 5, 2, 4, 3, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

3.2 Bubble Sort in C++

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {7, 5, 2, 4, 3, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

3.3 Bubble Sort in Java

public class BubbleSort {
    static void bubbleSort(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    public static void main(String args[]) {
        int arr[] = {7, 5, 2, 4, 3, 9};
        bubbleSort(arr);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

3.4 Bubble Sort in JavaScript

function bubbleSort(arr) {
    const n = arr.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                // Swap arr[j] and arr[j+1]
                const temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

const arr = [7, 5, 2, 4, 3, 9];
bubbleSort(arr);
console.log("Sorted array:", arr);

3.5 Bubble Sort in Python

def bubbleSort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                # Swap arr[j] and arr[j+1]
                arr[j], arr[j+1] = arr[j+1], arr[j]

arr = [7, 5, 2, 4, 3, 9]
bubbleSort(arr)
print("Sorted array:", arr)

4. Advantages of Bubble Sort

1. Bubble Sort is straightforward to understand and implement.
2. It requires only a constant amount of extra memory space.
3. It preserves the relative order of equal elements.

5. Disadvantages of Bubble Sort

1. Bubble Sort has poor time complexity, making it inefficient for large datasets.
2. It has a time complexity of O(n²), making it inefficient for large datasets.
3. It does not adapt to the data in any way. Even if the array is sorted, it will still perform O(n²) comparisons.

6. Time and Space Complexity of Bubble Sort

Time Complexity
Worst Case	O(n2)
Best Case	O(n)
Average Case	O(n2)
Space Complexity
Worst Case	O(1)

FAQs