What is Bubble Sort

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. The pass through the list is repeated until the list is sorted. The algorithm gets its name because smaller elements “bubble” to the top of the list.

Here’s a basic description of the Bubble Sort algorithm:

1. Start from the beginning of the list.
2. Compare each pair of adjacent elements. If they are in the wrong order (i.e., the element on the left is greater than the element on the right), swap them.
3. Continue this process until the end of the list. After the first pass, the largest element will have “bubbled up” to the end of the list.
4. Repeat the process for the remaining elements. On each pass, the next largest element will be placed in its correct position.
5. Continue until the entire list is sorted.

#include <iostream>
using namespace std;

void swap(int &a, int &b) {

    int temp = a;
    a = b;
    b = temp;
}

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 if the element found is greater
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

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

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

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

    bubbleSort(arr, n);

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

    return 0;
}

Despite its simplicity, Bubble Sort is not the most efficient sorting algorithm, especially for large datasets. Its average and worst-case time complexity are both O(n^2), where n is the number of elements in the list. There are more efficient sorting algorithms, such as Merge Sort or Quick Sort, which are often preferred for larger datasets.

Conclusion of Bubble Sort

In conclusion, Bubble Sort is a simple and straightforward sorting algorithm that works by repeatedly swapping adjacent elements until the entire list is sorted. While conceptually easy to understand and implement, Bubble Sort has several limitations:

1. Inefficiency: Bubble Sort has an average and worst-case time complexity of O(n^2), where n is the number of elements in the list. This makes it inefficient for large datasets.
2. Lack of adaptability: The algorithm does not adapt well to partially sorted lists. Even if a significant portion of the list is already sorted, Bubble Sort continues to perform passes through the entire list.
3. Not suitable for large datasets: Due to its quadratic time complexity, It becomes impractical for sorting large datasets. More efficient sorting algorithms, such as Merge Sort or Quick Sort, are often preferred in such cases.
4. Stability: It is a stable sorting algorithm, meaning that it maintains the relative order of equal elements. This can be an advantage in certain situations where maintaining the original order of equal elements is important.

In summary, while Bubble Sort is a good introductory algorithm for learning sorting concepts, it is generally not the preferred choice for real-world applications with large datasets. Other sorting algorithms with better average and worst-case time complexities are typically favored for efficiency reasons.

For more know contact us and check out Sahil Rawat’s I’d.