How Bubble Sort Works: A Simple Guide

Logic→

We take two nested loops the outer loop which will run from 0 to the length of items in array and the second loop running from 1 to the length of array - i times its doing so because if we run loop 1st time it will sort the loop keeping the biggest element at last index then again loops work it places the 2nd biggest element at 2nd last index so we are doing array.length-i as we know the i no of correct elements are placed correctly answer we don`t need to check them

then there is condition if previous element bigger than current element if yes then swap elements

Time Complexity of Bubble Sort:

1. Best Case (O(n)):

   • If the array is already sorted, bubble sort will perform only one pass through the array and exit early due to the optimization using the flag variable. In this case, the time complexity is O(n).

2. Worst Case (O(n²)):

   • When the array is sorted in reverse order, bubble sort will need to compare every adjacent pair of elements in all n passes through the array. Thus, the time complexity becomes O(n²).

3. Average Case (O(n²)):

   • On average, bubble sort will perform a number of comparisons and swaps proportional to the square of the array size, i.e., O(n²).

Space Complexity:

• O(1):
  Bubble sort is an in-place sorting algorithm, meaning it does not require any extra memory other than the input array itself. The space complexity is constant, O(1), as only a small, fixed amount of additional space is used for swapping elements.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1000, 1282, 88983, 684, 75, 96, 87, 68, 999, 100};
        System.out.println("Before Sorting: " + Arrays.toString(arr));

        // Bubble sort
        bubble(arr);
        System.out.println("After Sorting: " + Arrays.toString(arr));
    }

    static void bubble(int[] nums) {
        for (int i = 0; i < nums.length; i++) {  
            boolean flag = false;  // Reset flag for each pass
            for (int j = 1; j < nums.length - i; j++) {
                if (nums[j] < nums[j - 1]) {
                    // Swap elements if out of order
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                    flag = true;  // A swap has occurred
                }
            }
            if (!flag) {
                break;  // No swaps, so the array is sorted
            }
        }
    }
}

When to Use Bubble Sort:

1. Small Data Sets:

   • Bubble sort is simple to implement, and for small datasets (up to a few hundred elements), its inefficiency isn't very noticeable. It can be used when you want a simple sorting solution for small arrays or lists.

2. When Simplicity is More Important than Efficiency:

   • If you are working in an environment where the dataset is small or where you need an easy-to-understand solution with minimal code, bubble sort can be used, despite its inefficiency.

3. Nearly Sorted Data:

   • Bubble sort is somewhat efficient when the input array is almost sorted or has only a few elements out of order, because it can terminate early (with the optimization using the flag variable), potentially reducing the number of iterations.

When NOT to Use Bubble Sort:

1. Large Data Sets:

   • Bubble sort becomes inefficient for large datasets due to its O(n²) time complexity, especially if the dataset grows beyond a few hundred or thousand elements. For large data sets, you should use more efficient algorithms like Merge Sort, Quick Sort, or Heap Sort, which have O(n log n) complexity.

2. Real-Time or High-Performance Systems:

   • If the application is performance-sensitive, bubble sort is usually not suitable because of its high time complexity in the worst and average cases.

3. When Memory Efficiency is Critical:

   • If memory is not a constraint, bubble sort could still be used due to its in-place sorting nature. But if there are better algorithms with the same or similar memory footprint and significantly better time complexity, it's better to opt for those.

Alternatives to Bubble Sort:

• Quick Sort (Average: O(n log n))

• Merge Sort (Average: O(n log n))

• Insertion Sort (For small or partially sorted datasets: O(n²) worst-case, but better for nearly sorted arrays)