Bubble Sort is the simplest sorting algorithm. It works by iterating the input from the first to last.Comparing each pair and swapping them if needed. Bubble sort continues until no swapping needed.it got its name from the way smaller elements "bubble" to the top of the list.
2. Improved Method
package sorting;
public class BubbleSort {
static int a[];
public BubbleSort(int[] a) {
super();
this.a = a;
}
void simpleBubbleSort() {
int t = 0;
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {// swap
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
}
}
}
}
void advBubbleSort() {
int t = 0;
boolean flag = true;
for (int i = 0; i < a.length && flag; i++) {
flag = false;
for (int j = 0; j < a.length - 1; j++) {
if (a[j] > a[j + 1]) {// swap
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
flag = true;
}
}
}
}
static void printArray() {
for (int i : a) {
System.out.print(i + " ");
}
}
public static void main(String str[]) {
int arr[] = { 29, 6, 7, 8, 9, 1, 2, 3, 4, 5, 12 };
BubbleSort bs = new BubbleSort(arr);
double startTime = System.nanoTime();
bs.simpleBubbleSort();
printArray();
double endTime = System.nanoTime();
System.out.println("total time in naive method. -->"
+ (endTime - startTime));
startTime = System.nanoTime();
bs.advBubbleSort();
printArray();
endTime = System.nanoTime();
System.out.println("total time in advance method. -->"
+ (endTime - startTime));
}
}
1 2 3 4 5 6 7 8 9 12 29 total time in naive method. -->1025392.0 1 2 3 4 5 6 7 8 9 12 29 total time in advance method. -->436655.0