Bubble Sort Data Structure and Algorithm

Bubble Sort is a simple sorting algorithm that repeatedly steps through a list, compares adjacent elements, and swaps them if they are in the wrong order. It is called "Bubble Sort" because smaller elements "bubble" to the top of the list while larger elements "sink" to the bottom

Here's a step-by-step explanation of the Bubble Sort algorithm:

Algorithm:

Start at the beginning of the list.

Compare each pair of adjacent elements.

If the elements are in the wrong order (e.g., the current element is greater than the next one), swap them.

Move to the next pair of elements and repeat the process.

Continue these steps until no more swaps are needed, indicating that the list is sorted.

Pseudocode:

```
plaintext
```
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 in the inner loop, the array is already sorted
if (!swapped) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
System.out.println("Original Array:");
printArray(arr);
bubbleSort(arr);
System.out.println("Sorted Array:");
printArray(arr);
}
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}

In this Java implementation, the bubbleSort method takes an integer array as input and sorts it in ascending order using the Bubble Sort algorithm. The swapped flag is used to optimize the algorithm by breaking out of the loop early if no swaps are performed in a pass, indicating that the array is already sorted.

The main method contains an example array [5, 2, 9, 1, 5, 6], calls the bubbleSort method to sort it, and then prints both the original and sorted arrays using the printArray method.