Bubble Sort

Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order.

Starting from the first index, compare the first and the second elements. If the first element is greater than the second element, they are swapped. Now, compare the second and the third elements. Swap them if they are not in order.

The above process goes on until the last element. At this point, the largest value will have “bubbled up” to the last position.

Once the confirmed biggest value is its final position, a partition is created and that value doesn’t need to be compared again, saving processing time.

Example

( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Complexity

Bubble sort has a worst-case and average complexity of О(n^2), where n is the number of items being sorted.

The significant advantage that bubble sort has over most other algorithms is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n).

Code

function bubbleSort(items) {
  const swap = (firstIndex, secondIndex) => {
    const temp = items[firstIndex];
    items[firstIndex] = items[secondIndex];
    items[secondIndex] = temp;
  }

  const len = items.length;
  for (let i = 0; i < len; i++) {
    const stop = len - i;
    for (let j = 0; j < stop - 1; j++) {
      if (items[j] > items[j + 1]) {
        swap(j, j + 1);
      }
    }
  }

  return items;
}