Bubble Sort

Bubble Sort is a straightforward sorting algorithm that works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Although not the most efficient algorithm for large datasets, Bubble Sort’s simplicity makes it a useful educational tool for understanding sorting concepts.

How Bubble Sort Works:

Comparing and Swapping: Bubble Sort operates by comparing adjacent elements in the list and swapping them if they are in the wrong order. This iterative process continues until the entire list is sorted.

Passes: Each pass through the list ensures that the largest unsorted element “bubbles up” to its correct position. The number of passes required is one less than the total number of elements in the list.

Example: Consider the list [5, 2, 9, 1, 5, 6].

• In the first pass, the algorithm compares and swaps elements to move the largest element, 9, to the last position.
• In subsequent passes, the next largest elements move to their correct positions.

Time and Space Complexity

Time Complexity (O(n²)):

• In the worst case, Bubble Sort compares and swaps elements for each pair of elements in the array.
• The nested loops result in a time complexity of O(n²).

Space Complexity (O(1)):

• Bubble Sort uses a constant amount of additional memory space for variables.
• The space required does not grow with the size of the input array.

Advantages and Limitations of Bubble Sort:

Advantages:

1. Simple and Easy to Understand:

Bubble Sort is straightforward, making it easy for beginners to grasp its concept and implementation.

2. Stable and Adaptive:

• It is a stable algorithm, ensuring that equal elements maintain their relative order.
• Adaptive in the sense that it becomes more efficient when dealing with partially sorted data.

Limitations:

1. Inefficient for Large Datasets:

• Due to its quadratic time complexity, Bubble Sort becomes inefficient for large datasets.
• The number of comparisons and swaps grows quadratically with the size of the input.

2. Limited Practical Use:

• Bubble Sort is not as widely used in practical applications compared to more efficient sorting algorithms.
• Other algorithms, like Merge Sort or Quick Sort, are preferred for their better performance on larger datasets.

Example Java code for Bubble Sort

package sorting;

public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = { 11, 60, 5, 8, 29, 9, 33, 47, 78 };
        System.out.println("Unsorted array:");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
        System.out.println();
        bubbleSort(nums);

        System.out.println();
        System.out.println("Sorted array:");
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static void bubbleSort(int[] nums) {
        boolean swapped = true;
        while (swapped) {
            swapped = false;
            for (int i = 0; i < nums.length - 1; i++) {
                // if the current element is greater than the next element, swap them
                if (nums[i] > nums[i + 1]) {
                    // swap
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                    swapped = true;
                }
                System.out.println();
                for (int num : nums) {

                    System.out.print(num + " ");
                }
            }
        }
    }
}

Output

Unsorted array:
11 60 5 8 29 9 33 47 78

11 60 5 8 29 9 33 47 78
11 5 60 8 29 9 33 47 78
11 5 8 60 29 9 33 47 78
11 5 8 29 60 9 33 47 78
11 5 8 29 9 60 33 47 78
11 5 8 29 9 33 60 47 78
11 5 8 29 9 33 47 60 78
11 5 8 29 9 33 47 60 78
5 11 8 29 9 33 47 60 78
5 8 11 29 9 33 47 60 78
5 8 11 29 9 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 11 9 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
5 8 9 11 29 33 47 60 78
Sorted array:
5 8 9 11 29 33 47 60 78