Overview
Bubble sort is a simple sorting algorithm that repeatedly iterates through the array to be sorted, compares each pair of adjacent items, and swaps them. All sorting algorithms mostly have two fundamental operations:
1.Comparison.
2.Swapping.
Java program
In bubble sort we compare each element to the next element. If its greater than that element then we swap the two. The smallest value bubbles up to the top of the array. We pass through the array as many times as necessary to sort it.
public class BubbleSort {
public static void main(String args[]) {
int[] n = {45,16,21,79,106,99};
int no_of_iterations =0 ;
int no_of_swaps =0 ;
System.out.println("Array Before Bubble Sort:");
for (int aN : n) {
System.out.print(" | " + aN);
}
System.out.println();
// Bubble sort
for (int i=0; i < n.length; i++) {
for (int j=0; j < n.length - 1; j++) {
if (n[j] > n[j + 1]) {
int temp = n[j];
n[j] = n[j + 1];
n[j + 1] = temp;
no_of_swaps++;
}
no_of_iterations++;
}
no_of_iterations++;
}
System.out.println();
System.out.println("Array After Bubble Sort:");
for (int aN : n) {
System.out.print(" | " + aN);
}
System.out.println("");
System.out.println("Bubble Sort Program Statistics:");
System.out.println(" No of Iterations:"+ no_of_iterations);
System.out.println(" No of Swaps:"+ no_of_swaps);
}
}
Output of the program
Array Before Sort:
| 45 | 16 | 21 | 79 | 106 | 99
Array After Sort:
| 16 | 21 | 45 | 79 | 99 | 106
Bubble Sort Program Statistics:
No of Iterations:36
No of Swaps:3
We can further reduce the number of iterations by modifying the inner loop.
for (int i=0; i < n.length; i++) {
for (int j=0; j < n.length - i - 1; j++) {
if (n[j] > n[j + 1]) {
int temp = n[j];
n[j] = n[j + 1];
n[j + 1] = temp;
no_of_swaps++;
}
no_of_iterations++;
}
no_of_iterations++;
}
Array Before Sort:
| 45 | 16 | 21 | 79 | 106 | 99
Array After Sort:
| 16 | 21 | 45 | 79 | 99 | 106
Bubble Sort Program Statistics:
No of Iterations:21
No of Swaps:3