How do you implement a simple sorting algorithm using JavaScript?

Implementing a simple sorting algorithm is a fundamental computer science task. One of the easiest to understand is Bubble Sort. This algorithm repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

Bubble Sort Algorithm

Bubble Sort works by iterating over an array multiple times. In each pass, it compares adjacent elements and swaps them if they are in the wrong order. This process continues until no swaps are needed, indicating the array is sorted. Larger elements 'bubble up' to their correct positions with each pass.

JavaScript Implementation

function bubbleSort(arr) {
  const n = arr.length;
  let swapped;

  for (let i = 0; i < n - 1; i++) {
    swapped = false;
    for (let j = 0; j < n - 1 - i; j++) {
      // Compare adjacent elements
      if (arr[j] > arr[j + 1]) {
        // Swap them if they are in the wrong order
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // ES6 destructuring swap
        swapped = true;
      }
    }
    // If no two elements were swapped by inner loop, then break
    if (!swapped) {
      break;
    }
  }
  return arr;
}

How it Works

• The outer loop i controls the number of passes. After each pass, the largest unsorted element 'bubbles' to its correct position at the end of the unsorted part.
• The inner loop j iterates through the unsorted part of the array, comparing adjacent elements arr[j] and arr[j+1].
• If arr[j] is greater than arr[j+1], they are swapped using array destructuring.
• A swapped flag is used to optimize the algorithm. If an entire pass completes without any swaps, it means the array is already sorted, and we can break early.

Example Usage

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = bubbleSort(unsortedArray);
console.log(sortedArray); // Output: [11, 12, 22, 25, 34, 64, 90]

const anotherArray = [5, 1, 4, 2, 8];
console.log(bubbleSort(anotherArray)); // Output: [1, 2, 4, 5, 8]

While Bubble Sort is simple to understand, its time complexity is O(n^2) in the worst and average cases, making it inefficient for large datasets compared to more advanced algorithms like Merge Sort or Quick Sort.