Bubble sort is a straightforward sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the entire list is sorted.

Here’s how the basic bubble sort algorithm works:

1. Start with an unsorted list of elements.
2. Compare each pair of adjacent elements in the list.
3. If the elements are in the wrong order (e.g., the element on the left is greater than the element on the right), swap them.
4. Repeat steps 2 and 3 until no more swaps are needed.
5. The list is now sorted.

import java.util.Arrays;

class QuickSort {
    public static void main(String[] args) {
        int[] array = {8,4,2,9,12,5};
        sort(array);
        System.out.println(Arrays.toString(array));
    }
    public static void sort(int[] array){
        for (int i = 0; i < array.length; i++) {
            boolean swapable = false;
            for (int j = i+1; j < array.length; j++) {
                if (array[i] > array[j]) { 
                    int temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                    swapable = true;
                }
            }
            if (!swapable) {
                break;
            }
        }
    }
}

Now, let’s illustrate this with a step-by-step example using the array {8, 4, 2, 9, 12, 5}:

1. Initialization:
   • The array to be sorted is {8, 4, 2, 9, 12, 5}.
   • The outer loop starts from the first element and iterates through each element of the array.
2. First Pass (i = 0):
   • The outer loop starts with i = 0.
   • The inner loop compares each element with the element next to it (adjacent elements).
   • For each pair of adjacent elements, if the current element is greater than the next element, they are swapped.
   • After the first pass, the largest element (12) “bubbles up” to the end of the array.
   • The array becomes {4, 2, 8, 9, 5, 12}.
3. Second Pass (i = 1):
   • The outer loop continues with i = 1.
   • The inner loop compares each element with the element next to it (adjacent elements) starting from the second element.
   • In this pass, the second largest element (9) “bubbles up” to the second-last position in the array.
   • The array becomes {2, 4, 8, 5, 9, 12}.
4. Third Pass (i = 2):
   • The outer loop continues with i = 2.
   • The inner loop compares each element with the element next to it (adjacent elements) starting from the third element.
   • No swaps are needed in this pass because the array is already sorted.
   • The loop breaks early due to the swapable flag being false.
5. Array after Sorting:
   • After the third pass, the array is already sorted in ascending order.
   • The sorted array is {2, 4, 5, 8, 9, 12}.

Here are some key points to remember about the bubble sort algorithm:

1. Basic Idea: Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
2. Passes: In each pass of the algorithm, the largest unsorted element “bubbles up” to its correct position at the end of the array.
3. Complexity: Bubble sort is not efficient for large lists, as its average and worst-case time complexity are both O(n^2), where n is the number of elements in the list.
4. Stability: Bubble sort is a stable sorting algorithm, meaning that it preserves the relative order of equal elements.
5. In-Place Sorting: Bubble sort is an in-place sorting algorithm, meaning that it does not require extra space proportional to the size of the input array.
6. Optimization: The algorithm can be optimized by introducing a flag to track whether any swaps were made during a pass. If no swaps are made in a pass, the list is already sorted, and the algorithm can terminate early.
7. Usage: Due to its simplicity and ease of implementation, bubble sort is often used as an educational tool to introduce the concept of sorting algorithms. However, it is rarely used in practice for sorting large datasets due to its inefficiency.