Bozo Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Bozo Sort

A randomized educational sorting algorithm: checks if the array is sorted, and if not, swaps a single random pair of elements and repeats.

How it works

Bozo Sort is a cousin of Bogo Sort. Instead of randomly shuffling the entire array when it is unsorted (which scrambles everything), Bozo Sort swaps just two elements chosen at random. The steps are:

1. **Sorted Check:** Scan the list. If it is already sorted, exit.
2. **Random Swap:** If it is not sorted:
   • Generate two random indices \(i\) and \(j\) in the range \([0, n - 1]\).
   • Swap the values \(A[i]\) and \(A[j]\).
3. **Repeat:** Loop back to Step 1.

Though slightly less chaotic than Bogo Sort because it changes only two values at a time, Bozo Sort still relies entirely on chance and has an infinite worst-case time complexity.

Complexity

Interactive visualization

Pseudocode

procedure bozoSort(A):
  while not isSorted(A):
    i ← randomInteger(0, length(A) - 1)
    j ← randomInteger(0, length(A) - 1)
    swap(A[i], A[j])

JavaScript implementation

function bozoSort(arr) {
  while (!isSorted(arr)) {
    const i = Math.floor(Math.random() * arr.length);
    const j = Math.floor(Math.random() * arr.length);
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  return arr;
}

function isSorted(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    if (arr[i] > arr[i + 1]) return false;
  }
  return true;
}

Pros and cons

When (not) to use it

• Educational classes: Great for showing that making local random edits is slightly more efficient than fully scrambling a dataset (Bozo vs Bogo), though both remain completely impractical.
• Production systems: Never.