Imperative Way (Optimized)
public void bubbleSort(int[] a, int n) {
if (n <= 1) return
// execute n times
for (int i = 0; i < n; i++) {
boolean everyElementSmallerThanNextOne = true;
int k = i + 1; // times
int kthLargePosition = n - i - 1;
for (int j = 0; j < kthLargePosition; j++) {
if (a[j] > a[j + 1]) {
int tmp = a[j];
a[j] = a[j + 1];
a[j + 1] = tmp;
everyElementSmallerThanNextOne = false;
}
}
if (everyElementSmallerThanNextOne) break;
}
}
Functional Way (Not Optimized Yet)
bubbleToTop (x:y:remains)
| x > y = y : (bubbleToTop x : remains)
| otherwise = x : (bubbleToTop y : remains)
bubbleToTop (emptyOrSingleElement) = (emptyOrSingleElement)
bubble (list times)
| times == (length list) = list
| otherwise = bubble (bubbleToTop list) times + 1
bubbleSort list = bubble list 0
Functional Way (Optimized)
bubbleSort list = bubble list round_swap_happened=false 0
bubble (list round_swap_happened times)
| round_swap_happened == false = list
| times == (length list) = list
-- | every new round, the swap flage should be reset to false
| otherwise = bubble (bubbleToTop list round_swap_happened=false) times + 1
bubbleToTop (x:y:remains round_swap_happened)
-- | when it happens, update the flag
| x > y = y : (bubbleToTop x : remains round_swap_happened=true)
| otherwise = x : (bubbleToTop y : remains round_swap_happened)
bubbleToTop (emptyOrSingleElement) = (emptyOrSingleElement round_swap_happened)
