40.implement-Bubble-Sort.md

40. implement Bubble Sort

Problem

https://bigfrontend.dev/problem/implement-Bubble-Sort

Problem Description

Even for Front-End Engineer, it is a must to understand how basic sorting algorithms work.

Now you are asked to implement Bubble Sort, which sorts an integer array in ascending order.

Do it in-place, no need to return anything.

Follow-up

What is time cost for average / worst case ? Is it stable?

Solution

/**
 * @param {number[]} arr
 */
function bubbleSort(arr) {
  let hasNoSwaps;
  for (let i = arr.length; i >= 0; i--) {
    hasNoSwaps = true;
    for (let j = 0; j < i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        hasNoSwaps = false;
      }
    }
    if (hasNoSwaps) {
      break;
    }
  }
}