🧠

Bubble Sort

Bubble sort animation

  • Sinking sort
  • Similar to selection sort with a different scheme for finding min value
  • Compares successive elements, swapping whenever the bottom element is smaller than the one above it
  • Smallest element "bubbles up" to the front of the array
  • Each iteration puts the smallest unsorted element in its correct place
  • Inefficient but can quit early if partially sorted

Complexity

Average Time Space
O(n2)O(n^2) 11

Process

  • Repeatedly step through list
  • Compare each pair of adjacent elements --> swap if they are in the wrong order
  • Pass through the list until no swaps are needed

Implementations

JavaScript

function bubbleSort(array) {
  // Keep track if we swap an element
  let swapped = false;

  // Start looping through the entire array
  // i keeps track of how many elements are sorted
  for (let i = 1; i < array.length; i++) {
    // Each new element resets the swap tracker
    swapped = false;

    // Compare element with all remaining elements in array
    for (let j = 0; j < array.length - i; j++) {
      // If a smaller element is found, swap in place
      if (array[j + 1] < array[j]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];

        // Mark as swapped
        swapped = true;
      }
    }

    // Return early if nothing is swapped
    if (!swapped) {
      return array;
    }
  }

  return array;
}

Computer Science Algorithm

Backlinks