Bubble sort

Bubble sort is a sorting algoritm that compares two adjacent elements and swaps them until they are in the intended order. Just like the movement of air bubbles in the water that rise up to the surface, each element of the array moves to the end in each iteration. Therefore, it is called a bubble sort.

Working of Bubble Sort Suppose we are trying to sort the elements in ascending  order.

1. First Iteration (Compare and Swap)
2. Starting from the first index, compare the first and the second elements.
3. If the first element is greater than the second element, they are swapped.
4. Now, compare the second and the third elements. Swap them if they are not in order.
5. The above process goes on until the last element

Pass 1:

Compare 5 and 3 → swap → [3, 5, 8, 4, 1, 12, 7]
Compare 5 and 8 → no swap → [3, 5, 8, 4, 1, 12, 7]
Compare 8 and 4 → swap → [3, 5, 4, 8, 1, 12, 7]
Compare 8 and 1 → swap → [3, 5, 4, 1, 8, 12, 7]
Compare 8 and 12 → no swap → [3, 5, 4, 1, 8, 12, 7]
Compare 12 and 7 → swap → [3, 5, 4, 1, 8, 7, 12]

Pass 2:

Compare 3 and 5 → no swap
Compare 5 and 4 → swap → [3, 4, 5, 1, 8, 7, 12]
Compare 5 and 1 → swap → [3, 4, 1, 5, 8, 7, 12]
Compare 5 and 8 → no swap
Compare 8 and 7 → swap → [3, 4, 1, 5, 7, 8, 12]

Pass 3:

Compare 3 and 4 → no swap
Compare 4 and 1 → swap → [3, 1, 4, 5, 7, 8, 12]
Compare 4 and 5 → no swap
Compare 5 and 7 → no swap

Pass 4:

Compare 3 and 1 → swap → [1, 3, 4, 5, 7, 8, 12]
Compare 3 and 4 → no swap
Compare 4 and 5 → no swap

Pass 5:

Compare 1 and 3 → no swap
Compare 3 and 4 → no swap

Final Sorted Array:
[1, 3, 4, 5, 7, 8, 12]

Bubble sort Java code:

public class BubbleSort {

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

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

            // Inner loop for comparison
            for (int j = 0; j  arr[j + 1]) {

                    // Swap elements
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;

                    swapped = true;
                }
            }

            // If no swapping happened, array is sorted
            if (!swapped) {
                break;
            }
        }
    }

    // Function to print array
    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

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

        System.out.println("Before Sorting:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("After Sorting:");
        printArray(arr);
    }
}

Time Complexity of Bubble Sort:

Space Complexity:

• O (1) (in-place sorting, no extra space used)

Note: Bubble Sort is simple but inefficient for large datasets due to its quadratic time complexity in most cases. It is mainly used for educational purposes.