Bubble Sort

How It Works?

• Compare adjacent elements in a list.
• Swap them if the first element is greater than the second.
• Repeat this process through the entire list until no more swaps are needed.
• The largest values “bubble up” to the end of the list with each pass.

The Bubble Effect

Bubble sort works by passing through the list over and over. Every time a large number encounters a smaller number next to it, the swap forces the larger number one step further to the right. Over multiple passes, the largest numbers gradually “bubble up” to their correct final positions at the end of the array.

Implementation

JavaScript

function bubbleSort(array) {
  const n = array.length - 1;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }

  return array;
}

console.log(bubbleSort([99, 44, 6, 2, 1, 5]));
// Output: [1, 2, 5, 6, 44, 99]

Python

def bubbleSort(array):
  n = len(array) - 1

  for i in range(n):
      for j in range(n - i):
          if array[j] > array[j + 1]:
              array[j], array[j + 1] = array[j + 1], array[j]

  return array

print(bubbleSort([99, 44, 6, 2, 1, 5]))
# Output: [1, 2, 5, 6, 44, 99]

Optimized Bubble Sort

Standard bubble sort always runs through its loops a fixed number of times. Even if you give it an already sorted list like [1, 2, 3, 4, 5], it will blindly compare every adjacent pair over and over until the loops finish. This wastes processing power.

Optimized bubble sort with a swapped flag is a modification that stops the algorithm early if the array becomes fully sorted before all loops finish.

How the swapped flag fixes it?

The optimized version introduces a boolean variable (a flag) to monitor the sorting process:

• Reset the flag: At the start of each outer loop pass, set swapped = False.
• Track the actions: If the inner loop finds elements out of order and swaps them, change swapped = True.
• Check the status: After a full pass through the array, check the flag. If swapped is still False, it means no numbers were swapped.
• Exit early: If no swaps happened, the list is officially sorted. The algorithm immediately breaks out of the loop and stops.

JavaScript

function bubbleSortOptimized(array) {
  const n = array.length - 1;

  for (let i = 0; i < n; i++) {
    let swapped = false;

    for (let j = 0; j < n - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return array;
}

console.log(bubbleSortOptimized([99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]));
// Output: [0, 1, 2, 4, 5, 6, 44, 63, 87, 99, 283]

Python

def bubbleSortOptimized(array):
  n = len(array) - 1

  for i in range(n):
      swapped = False

      for j in range(n - i):
          if array[j] > array[j + 1]:
              array[j], array[j + 1] = array[j + 1], array[j]
              swapped = True
      if not swapped:
          break

  return array

print(bubbleSortOptimized([99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0]))
# Output: [0, 1, 2, 4, 5, 6, 44, 63, 87, 99, 283]

Complexity and Features

• Time Complexity:
  • O(n²) for average and worst cases
  • O(n) for best case when the array is already sorted.
• Space Complexity: O(1) because it sorts in-place without extra memory.
• Stable: Equal elements keep their original order