Bubble Sort

Why did the bubble sort algorithm go to therapy? Because it had too many issues to sort out one at a time!

What is Bubble Sort?

Bubble Sort is a straightforward, comparison-based sorting algorithm. It 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 no swaps are needed, indicating that the list is sorted. Bubble Sort is named for the way smaller elements "bubble" to the top of the list during each pass.

How does it work?

Here's a step-by-step explanation of how Bubble Sort works:

1. Start at the beginning of the list.

2. Compare the first two elements. If the first element is larger than the second, swap them.

3. Move to the next pair of elements and repeat the comparison and swapping process.

4. Continue this process until you reach the end of the list.

5. Repeat steps 1-4 for each element in the list, one pass at a time.

6. After each pass, the largest unsorted element will have "bubbled up" to the end of the list.

7. Repeat the process for the remaining unsorted elements until no swaps are needed, indicating that the list is sorted.

Bubble Sort is relatively simple to implement but not very efficient, especially for large datasets. It has a worst-case and average time complexity of O(n^2), making it less suitable for sorting large lists compared to more efficient sorting algorithms like Quick Sort or Merge Sort.

Bubble Sort Code in Java:

public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};

        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;
                }
            }
        }

        System.out.println("Sorted array:");
        for (int value : arr) {
            System.out.print(value + " ");
        }
    }
}

Bubble Sort Code 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[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    bubbleSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Time and Space Complexity Analysis

The time complexity of Bubble Sort can be expressed mathematically as follows:

Let n be the number of elements in the array to be sorted.

• In the worst case, Bubble Sort makes n - 1 passes through the entire array. In each pass, it compares and possibly swaps adjacent elements.

• In the first pass, it compares n - 1 pairs of elements.

• In the second pass, it compares n - 2 pairs.

• In the third pass, it compares n - 3 pairs.

• ...

• In the (n-1)-th pass, it compares 1 pair.

The total number of comparisons in the worst case can be calculated as the sum of the first (n-1) natural numbers, which is given by the formula:

$(1 + 2 + 3 + ... + (n-1) = \frac{n \cdot (n-1)}{2})$

So, in the worst case, the number of comparisons made by Bubble Sort is approximately:

$(\frac{n \cdot (n-1)}{2})$

Therefore, the worst-case time complexity of Bubble Sort can be mathematically expressed as:

$(T(n) = \frac{n \cdot (n-1)}{2} \approx \frac{n^2}{2})$

Asymptotically, the worst-case time complexity of Bubble Sort is O(n^2), which indicates that its performance degrades quadratically with the size of the input array. This makes Bubble Sort inefficient for large datasets compared to more efficient sorting algorithms like Quick Sort or Merge Sort, which have better average and worst-case time complexities.

So, the time complexity of Bubble sort is:

• Worst-case: O(n^2)

• Average-case: O(n^2)

• Best-case (with optimized version): O(n)

And the space complexity: O(1) (in-place sorting, no additional memory required)

Again, Bubble Sort is primarily used for educational purposes and is not recommended for sorting large datasets due to its quadratic time complexity.