WikiGalaxy
Bubble Sort Overview
Introduction to Bubble Sort
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.
Example 1: Ascending Order
Sorting an Array in Ascending Order
In this example, we will sort an array of integers in ascending order using Bubble Sort. The algorithm compares each pair of adjacent items and swaps them if they are in the wrong order.
public class BubbleSortExample {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 1, 5, 6};
bubbleSort(arr);
System.out.println("Sorted Array: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
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;
}
}
}
}
}
Console Output:
1 2 5 5 6 9
Example 2: Descending Order
Sorting an Array in Descending Order
This example demonstrates how to modify the Bubble Sort algorithm to sort an array in descending order by changing the comparison condition.
public class BubbleSortDescending {
public static void main(String[] args) {
int[] arr = {3, 8, 7, 5, 2};
bubbleSortDescending(arr);
System.out.println("Sorted Array in Descending Order: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
static void bubbleSortDescending(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
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;
}
}
}
}
}
Console Output:
8 7 5 3 2
Example 3: Optimized Bubble Sort
Optimizing Bubble Sort with a Flag
The optimized version of Bubble Sort stops the algorithm if the inner loop didn't cause any swap, indicating that the array is already sorted.
public class OptimizedBubbleSort {
public static void main(String[] args) {
int[] arr = {2, 3, 4, 5, 6};
bubbleSortOptimized(arr);
System.out.println("Optimized Sorted Array: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
static void bubbleSortOptimized(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 (!swapped) break;
}
}
}
Console Output:
2 3 4 5 6
Example 4: Bubble Sort on Strings
Sorting an Array of Strings
Bubble Sort can also be used to sort an array of strings. In this example, we'll sort strings in alphabetical order.
public class BubbleSortStrings {
public static void main(String[] args) {
String[] arr = {"apple", "orange", "banana", "grape"};
bubbleSortStrings(arr);
System.out.println("Sorted Strings: ");
for (String s : arr) {
System.out.print(s + " ");
}
}
static void bubbleSortStrings(String[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j].compareTo(arr[j+1]) > 0) {
// swap arr[j] and arr[j+1]
String temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
}
Console Output:
apple banana grape orange
Example 5: Bubble Sort with Early Exit
Implementing Early Exit in Bubble Sort
An early exit mechanism can be implemented in Bubble Sort to stop the algorithm when the array is already sorted before completing all passes.
public class BubbleSortEarlyExit {
public static void main(String[] args) {
int[] arr = {10, 20, 30, 40, 50};
bubbleSortEarlyExit(arr);
System.out.println("Sorted Array with Early Exit: ");
for (int i : arr) {
System.out.print(i + " ");
}
}
static void bubbleSortEarlyExit(int[] arr) {
int n = arr.length;
for (int i = 0; i < n-1; i++) {
boolean 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 (!swapped) break;
}
}
}
Console Output:
10 20 30 40 50
