Explain bubble sort and its implementation in Java JDK 22

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. The pass through the list is repeated until the list is sorted. It is named for the way smaller elements “bubble” to the top of the list with each iteration.

Here’s a basic implementation of the bubble sort algorithm in Java:

public class BubbleSort {
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
bubbleSort(array);
System.out.println("Sorted array:");
for (int num : array) {
System.out.print(num + " ");
}
}

public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
// Swap array[j] and array[j+1]
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}

This implementation consists of two nested loops. The outer loop iterates from the first element to the second-to-last element of the array, and the inner loop iterates from the first element to the element just before the current outer loop index. Within the inner loop, adjacent elements are compared, and if they are out of order, they are swapped.

The time complexity of bubble sort is O(n^2) in the worst and average cases, making it inefficient on large lists. However, it is simple to understand and implement, which makes it useful for educational purposes or for sorting small datasets where performance is not critical.