Bubble sort has best-case complexity O(n). When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. Thus bubblesort will make only n comparisons and determine that list is completely sorted. It will also use considerably less time O(n2) than if the elements in the unsorted list are not too far from their sorted places.
public class BubbleSort {
int[] data;
public BubbleSort(int[] data) {
super();
this.data = data;
}
public int[] sort() {
boolean isSwap = false;
int temp = 0;
do {
isSwap = false;
for (int i = 0; i data[i + 1]) {
temp = data[i];
data[i] = data[i + 1];
data[i + 1] = temp;
isSwap = true;
}
}
} while (isSwap);
return data;
}
/**
* instead of doing n2 comparisons (and swaps), we can use only
* n + (n-1) + (n-2) + ... + 1 comparisons.
* This sums up to n(n + 1) / 2, which is still
* O(n2), but which can be considerably faster in practice.
*
* @return sorted data
*/
public int[] optimezedSort() {
boolean isSwap = false;
int temp = 0;
int n = data.length - 1;
do {
isSwap = false;
n = n - 1;
for (int i = 0; i data[i + 1]) {
temp = data[i];
data[i] = data[i + 1];
data[i + 1] = temp;
isSwap = true;
}
}
} while (isSwap);
return data;
}
public static void main(String[] args) {
int[] data = new int[] {1,2,3,4,5,8,6,9,7};
System.out.println(Arrays.toString(new BubbleSort(data).sort()));
System.out.println(Arrays.toString(new BubbleSort(data).optimezedSort()));
}
}