Оптимизированная пузырьковая сортировка в Javascript

Обычная пузырьковая сортировка имеет временную сложность O(n²).
Но, конечно, мы можем написать пузырьковую сортировку значительно оптимизированным способом, который можно действительно использовать с большими данными.
Также можно задать вопрос. в нескольких интервью.

Общий алгоритм пузырьковой сортировки

const commonBubblesort = (arr) => {
let swaps;
do {
 swaps = false;
 for(let i=0;i<arr.length;i++){
  if(arr[i]>arr[i+1]){
  let temp = arr[i];
  arr[i] = arr[i+1];
  arr[i+1] = temp;
  swaps = true;
  }
 }
}while(swaps)
return arr;
}

Оптимизированный алгоритм пузырьковой сортировки

const optimizedBubblesort = (a) => {
let lastSwap = a.length - 1;
for (let i = 1; i< a.length; i++) {
 let is_sorted = true;
 let currentSwap = -1;
 for (let j = 0; j < lastSwap; j++) {
  if (a[j] > a[j+1]) {
  let temp = a[j];
  a[j] = a[j+1];
  a[j+1] = temp;
  is_sorted = false;
  currentSwap = j;
  }
 }
if (is_sorted) break;
lastSwap = currentSwap;
}
return a;
}

Использование функции Do while

const commonBubblesort = (arr) => {
let swaps;
let lastSwap = arr.length - 1;
do {
swaps = false;
let currentSwap = -1;
for(let i=0;i<lastSwap;i++){
if(arr[i]>arr[i+1]){
let temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
swaps = true;
currentSwap = i;
}
}
lastSwap = currentSwap;
}while(swaps)
return arr;
}

Это позволяет пропускать многие элементы, что в худшем случае приводит к увеличению количества сравнений примерно на 50% (хотя и без улучшения количества подкачек), и добавляет очень мало сложности. Поскольку мы вспоминаем, где был наш последний обмен, и знаем, что остальные больше, чем этот.