Sorting algorithms: Bubble Sort

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. The process is repeated until the list is sorted.

How it works:

1. Initial Pass:

   • Starting from the beginning of the array, compare the first two elements.

   • If the first element is larger than the second, swap them.

   • Move to the next pair and repeat the comparison and swap if necessary.

   • Continue this process until you reach the end of the array. After this pass, the largest element will be at the last position in the array.

2. Subsequent Passes:

   • Repeat the process for the remaining elements (ignoring the last sorted elements).

   • Each pass "bubbles" the next-largest element to its correct position.

3. Completion:

   • The process continues until no swaps are needed during a pass, which means the array is sorted.

    // Function to perform Bubble Sort
        public static void bubbleSort(int[] arr) {
            int n = arr.length;
            boolean swapped;

            // Outer loop for all passes
            for (int i = 0; i < n - 1; i++) {
                swapped = false;

                // Inner loop to compare adjacent elements
                for (int j = 0; j < n - i - 1; j++) {
                    // Compare adjacent elements
                    if (arr[j] > arr[j + 1]) {
                        // Swap if the elements are in the wrong order
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                        swapped = true;
                    }
                }

                // If no two elements were swapped, array is sorted
                if (!swapped) {
                    break;
                }
            }
        }

Explanation:

1. bubbleSort :

   • It iterates through the array and compares adjacent elements.

   • If the element on the left is greater than the element on the right, they are swapped.

   • The process repeats until the array is sorted.

2. Optimization:

   • The swapped flag is used to check if a swap was made during a pass. If no swap is made, the array is already sorted, and the algorithm can terminate early.

Complexity

Time Complexity:

• Best case (already sorted): O(n)

• Average case: O(n²)

• Worst case: O(n²)

Space Complexity:

• Space Complexity: O(1) – In-place sorting, so no extra space is needed aside from a few temporary variables

When to Use Bubble Sort:

While Bubble Sort is generally inefficient for large datasets due to its O(n2)O(n^2)O(n2) time complexity, it can be useful in certain specific scenarios:

Small Data Sets , Nearly Sorted Data ,Educational Purposes (as it is simple algorithm)

When Not to Use Bubble Sort:

1. Large Data Sets : Bubble Sort becomes highly inefficient for large data sets due to its O(n2)O(n^2)O(n2) time complexity.

2. Time-Sensitive Applications (slow sorting performance)