Bubble Sort in C, C++, and Java | Code & Explanation

In this article, we will discuss the Bubble Sort algorithm in C, C++, and Java. We will cover the Bubble Sort example, its algorithm implementation, time complexity analysis, and its advantages and disadvantages.

What is Bubble Sort?

Bubble Sort is a simple sorting algorithm that repeatedly steps through a given array, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the array is sorted in ascending order.

Key Features:

• It compares each pair of adjacent elements and swaps them if necessary.
• The largest element bubbles up to the end of the array after each iteration.
• The process is repeated (n-1) times for an array of size n.

Bubble Sort Explanation with Example

Consider the following array of 5 elements:

Unsorted Array: [5, 3, 8, 4, 2]

Step-by-Step Execution:

First Pass:

1. Compare 5 and 3, swap → [3, 5, 8, 4, 2]
2. Compare 5 and 8, no swap → [3, 5, 8, 4, 2]
3. Compare 8 and 4, swap → [3, 5, 4, 8, 2]
4. Compare 8 and 2, swap → [3, 5, 4, 2, 8]

After the first iteration, the largest element (8) is at the correct position.

The process continues for n-1 iterations until the array is fully sorted.

Sorted Array: [2, 3, 4, 5, 8]

Since sorting requires multiple passes, Bubble Sort is inefficient for large datasets.

Bubble Sort Algorithm (Pseudo Code)

for i = 0 to n-1:
   for j = 0 to n-i-1:
      if arr[j] > arr[j+1]:
         swap(arr[j], arr[j+1])

This algorithm runs for n-1 iterations, where n is the number of elements.

Bubble Sort Implementation

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]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

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], arr[j+1]);
            }
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: \n";
    printArray(arr, n);
    return 0;
}

Bubble Sort in Java

import java.util.Arrays;

public class BubbleSort {
    public 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]) {
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    public static void main(String args[]) {
        int arr[] = {5, 3, 8, 4, 2};
        bubbleSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Optimized Bubble Sort

The basic Bubble Sort has a worst-case time complexity of O(n²), even when the array is already sorted. To optimize it, we introduce a flag that checks if a swap occurs. If no swaps happen, the array is already sorted, and we can exit early.

void optimizedBubbleSort(int arr[], int n) {
    bool swapped;
    for (int i = 0; i < n-1; i++) {
        swapped = false;
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                swap(arr[j], arr[j+1]);
                swapped = true;
            }
        }
        if (!swapped)
            break;
    }
}

This reduces unnecessary iterations, improving efficiency when the array is nearly sorted.

Bubble Sort Time & Space Complexity

• Space Complexity: O(1) (in-place sorting algorithm)

Why is Bubble Sort Inefficient?

• Performs many unnecessary swaps and comparisons.
• Slow for large datasets.
• Other sorting algorithms like Quick Sort, Merge Sort, and Heap Sort perform significantly better.

Conclusion

Bubble Sort is a simple algorithm that is easy to understand and implement but is inefficient for large datasets. While it can be useful for small lists or educational purposes, other sorting algorithms like Merge Sort or Quick Sort are preferred for performance-critical applications.

Related Sorting Algorithms

• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort