Bubble sort algorithm doesn’t track the current state of the array.

Even if it gets the fully sorted array as an input, the runtime will remain of the same O(n^2^) complexity. By design this algorithm analyses all the adjacent pairs of elements of the original array n times where n is the length of an array.

Optimized bubble sort

The bubble sort algorithm doesn’t keep track of the current state of the array in any way.

Even if we send an already sorted array as input, we will need the same number of loop iterations as for an unsorted array to get the result.

Performance can be improved by adding a flag (boolean variable) that will monitor whether there was at least one exchange at the current iteration.

If not, then the array is sorted and the task is complete.

const optimizedBubbleSort = (arr) => {
  let hasSwapped = false;
  let outerLoopIterationCount = 0;
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        hasSwapped = true;
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    if (!hasSwapped) {
      return outerLoopIterationCount;
    } else {
      hasSwapped = false;
    }
    outerLoopIterationCount++;
  }
  return outerLoopIterationCount;
}

Let’s take two arrays to check the implementation. The second one is twice as long as the first one, but it has only one element out of place.

  • display the initial state of the arrays
  • we sort them and save the number of iterations that the optimizedBubbleSort sort function will return
  • display the arrays again to make sure that they are sorted and check the number of iterations it took to sort
const testData = [ 0, -1, 4, 5, 2, -3 ];
const almostSortedTestData = [ 12, -3, -1, 0, 2, 4, 5, 7, 8, 9, 10 ];

console.log(testData, `Initial testData state`);
console.log(almostSortedTestData, `Initial almostSortedTestData state`);

const iterationsTestData = optimizedBubbleSort(testData);
const iterationsAlmostSortedTestData = optimizedBubbleSort(almostSortedTestData);

console.log(testData, `Total iterations: ${iterationsTestData}`);
console.log(almostSortedTestData, `Total iterations: ${iterationsAlmostSortedTestData}`);

The console output is:

[ 0, -1, 4, 5, 2, -3 ] Initial testData state
[ 12, -3, -1, 0, 2, 4, 5, 7, 8, 9, 10 ] Initial almostSortedTestData state

[ -3, -1, 0, 2, 4, 5 ] Total iterations: 6
[ -3, -1, 0, 2,  4, 5, 7, 8, 9, 10, 12 ] Total iterations: 2

Although the second array turned out to be 2 times longer than the first one, we only needed two iterations of the outer loop to sort it.

On the second pass, the hasSwapped flag has not changed. This means that there were no exchanges and the array has already been sorted. We completed the optimized bubble sort algorithm right away and wasted no extra time.

By the way, if we try to sort an array in which all elements are already arranged in ascending order using the optimizedBubbleSort function, then we will need only one iteration of the outer loop. So at best we get O(n) runtime complexity.

const testData = [ 0, 1, 2, 3, 4, 5, 6 ];

console.log(testData, `Initial testData state`);

const iterationsTestData = optimizedBubbleSort(testData);

console.log(testData, `Total iterations: ${iterationsTestData}`);

Вывод на экран:

[ 0, 1, 2, 3, 4, 5, 6 ] Initial testData state
[ 0, 1, 2, 3, 4, 5, 6 ] Total iterations: 1

Cocktail sort

Cocktail sort is another enhancement of the bubble sort. Alternative names for this sorting algorithm are shaker sort or bidirectional sort.

We start in exactly the same way as in the bubble sort, and “push up” the maximum element. After that, we unfold and “push down” the minimum of the remaining elements.

Once we get to the beginning of the array, there will already be 2 elements in their places - the first and the last one. Thus, we will make 2 times less iterations of the outer loop. Due to this, the speed of the cocktail sort will be slightly higher than that of the bubble sort.

We’ll start with the small refactoring and extract the exchange function from our algorithm. We’ll call it swap :

function swap(arr, i, j) {
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

Then, we implement the cocktail sort in JavaScript:

function cocktailSort(arr) {
  let left = 0;
  let right = arr.length - 1;
  let hasSwapped = false;
  let outerLoopIterationCount = 0;

  while (left < right) {
    outerLoopIterationCount++;
    for (let i = left; i < right; i++) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);
        hasSwapped = true;
      }
    }
    right--;
    for (let i = right; i > left; i--) {
      if (arr[i] < arr[i - 1]) {
        swap(arr, i, i - 1);
        hasSwapped = true;
      }
    }
    left++;
    if (!hasSwapped) {
      return outerLoopIterationCount;
    } else {
      hasSwapped = false;
    }
  }
  return outerLoopIterationCount;
}

And, using the same array, let’s make sure that there are indeed 2x less iterations of the outer loop:

const testData = [ 0, -1, 4, 5, 2, -3 ];

console.log(testData, `Initial testData state`);
const iterationsTestData = cocktailSort(testData);
console.log(testData, `Total iterations: ${iterationsTestData}`);

As you see, the array is sorted and total iterations is 3 instead of 6 for the optimizedBubbleSort:

[ 0, -1, 4, 5, 2, -3 ] Initial testData state
[ -3, -1, 0, 2, 4, 5 ] Total iterations: 3

Read more JavaScript tutorials or Learn Full-Stack JS from scratch!