JavaScript Algorithms: Bubble Sort

Bubble sort is a simple sorting algorithm with an inefficient worst-case time complexity of O(n^2). However, it is still worth learning about the algorithm.

Bubble sort works by looping through an array and comparing each item to the one next to it. If the item on the right is smaller, the two positions are swapped.

Here is an implementation of the bubble sort algorithm:

const bubbleSort = (originalArray) => {
  let swapped = false;
  
  const array = [...originalArray];
  
  for (let i = 1; i < array.length - 1; i++) {
    swapped = false;
    
    for (let j = 0; j < array.length - i; j++) {
      if (array[j + 1] < array[j]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
        swapped = true;
      }
    }
    
    if (!swapped) {
      return array;
    }
  }
  
  return array;
}

The O(n^2) complexity arises from the fact that we loop through the array twice to check if we need to swap elements.

The process begins with comparing the first element with the second. If the first element is larger, they are swapped. Otherwise, the elements are left as-is and the comparison is made with the second and third elements. This process continues until each element finds its correct position in the array.

Here is an example:

Suppose we run bubbleSort([2, 1, 3]).

First, we compare 2 with 1. Since 2 is greater than 1, we swap them:

1 2 3

Next, we compare 2 with 3. Since 2 is less than 3, we leave it as-is. We skip the last element since, based on our workflow, it will always be the largest element.

Tags: JavaScript, Bubble Sort, Sorting Algorithm, Time Complexity, Optimization