Bubble Sort Explanation

Bubble Sort is a simple comparison-based sorting algorithm. It 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. It gets its name because smaller elements "bubble" to the top of the list, while larger elements sink to the bottom.

Algorithm Steps:

1. Start at the beginning of the array.
2. Compare the first element with the next one.
3. If the current element is larger than the next element, swap them.
4. Move to the next pair and repeat the comparison and swapping until the end of the array.
5. The last element will be in its correct position after the first pass.
6. Repeat this process for the rest of the array until no more swaps are needed.

Advantages:

• Simple and easy to implement.
• No extra space is required (in-place sorting).
• Efficient for small data sets or nearly sorted data.

Disadvantages:

• Inefficient on large datasets as the time complexity is O(n2).
• Performs poorly compared to more advanced algorithms like Quick Sort or Merge Sort.
• Repeatedly iterates over the array even if it’s already sorted.

Code Implementations:

C++ Code:

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        bool 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 no elements were swapped, the array is already sorted
        if (!swapped)
            break;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "Sorted array: \n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java Code:

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            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;
                    swapped = true;
                }
            }
            // If no elements were swapped, the array is sorted
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

Python Code:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, 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]
                swapped = True
        # If no elements were swapped, the array is sorted
        if not swapped:
            break

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

Time Complexity:

• Best case: O(n) (when the array is already sorted).
• Average and worst case: O(n2).

Bubble Sort is generally not recommended for large datasets due to its inefficiency compared to more advanced algorithms. However, its simplicity makes it a good choice for teaching sorting concepts.