1. Introduction

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Its name comes from the way smaller elements “bubble” to the top of the list.

2. Program Steps

1. Start from the first element of the array.

2. Compare the current element with the next element.

3. If the current element is greater than the next element, swap them.

4. Move to the next element and repeat the above steps until the end of the array is reached.

5. After each complete pass, the largest element will have “bubbled up” to its correct position.

6. Repeat the entire process for the array until no more swaps are needed.

3. Code Program

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            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;
                    swapped = true;
                }
            }
            // If no two elements were swapped by inner loop, then the array is sorted
            if (!swapped) break;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array:");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output:

Sorted array:
11 12 22 25 34 64 90

4. Step By Step Explanation

1. The function bubbleSort accepts an integer array arr as its parameter.

2. The outer loop (i loop) represents the number of passes required to ensure the array is sorted.

3. The inner loop (j loop) is responsible for the pairwise comparisons. Within this loop, adjacent elements are compared, and if they are in the wrong order, they are swapped.

4. swapped is a flag that helps in optimizing the algorithm. If in a pass, no elements were swapped, it means the array is already sorted and there's no need for further passes.

5. In the main method, a sample array is sorted using the bubbleSort method and the sorted array is printed to the console.

The Bubble Sort algorithm is easy to understand and implement, but it is not suitable for large datasets because of its O(n^2) average and worst-case time complexity.