Bubble Sort: Imperative vs Funti

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)