40.implement-Bubble-Sort.md

40. implement Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process continues until the list is sorted.

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;
    }
  }
}

// Usage 
console.log(bubbleSort([37, 45, 29, 8, 12, 88, -3])); // [-3, 8, 12, 29, 37, 45, 88]
console.log(bubbleSort([8, 1, 2, 3, 4, 5, 6, 7])); // [1, 2, 3, 4, 5, 6, 7, 8]
console.log(bubbleSort([1, 2, 3, 4, 5, 6, 7, 8])); // [1, 2, 3, 4, 5, 6, 7, 8]

Use Cases:

1. Small Data Sets: It can be useful for small datasets or when the simplicity of the implementation is more critical than performance.
2. Nearly Sorted Data: If the data is nearly sorted or has only a few elements out of order, Bubble Sort can be efficient.