medium

Sort an Array of 0s, 1s, and 2s Using Adjacent Swaps

Sort an array of only 0, 1, and 2 values using bubble sort-style adjacent swaps.

1. Define the problem

Sort an Array of 0s, 1s, and 2s Using Adjacent Swaps

Given an array nums containing only the values 0, 1, and 2, sort it in ascending order using only adjacent swaps . Unlike the one-pass partitioning trick for this kind of array, solve it here with bubble sort's repeated compare-and-swap passes — the same technique works no matter how many distinct values the array holds.

Constraints

  • 1 ≤ nums.length ≤ 1000
  • numsi is 0, 1, or 2

Example

Inputnums = [2, 0, 2, 1, 1, 0]
Output[0, 0, 1, 1, 2, 2]

Explanation Repeated adjacent swaps move every 0 to the front and every 2 to the back.

2. Visualize the solution

Bubble sort a three-value array

Bubble sort a three-value array
Statusstart

Initial array [2, 0, 2, 1, 1, 0].

What happens in this step

[2, 0, 2, 1, 1, 0]

Sorting begins with the full array unsorted; pass 1 will compare each neighbor pair left to right, just like with any other values.
Step 1 of 3

Steps to visualize

  1. Walk the array comparing each pair of neighbors.
  2. Swap whenever the left value is bigger than the right value — this works the same whether the values are 0, 1, 2, or anything else.
  3. Repeat passes, shrinking the unsorted region each time, until a pass makes no swaps.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Bubble sort a three-value array
Statusstart

Initial array [2, 0, 2, 1, 1, 0].

What happens in this step

[2, 0, 2, 1, 1, 0]

Sorting begins with the full array unsorted; pass 1 will compare each neighbor pair left to right, just like with any other values.
Step 1 of 3
4. Solution

Solution

solution.tsTypeScript
function sortZeroOneTwo(nums) {
  const arr = nums.slice();
  const n = arr.length;

  for (let pass = 0; pass < n - 1; pass++) {
    let swapped = false;

    for (let i = 0; i < n - 1 - pass; i++) {
      if (arr[i] > arr[i + 1]) {
        const temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }

    if (!swapped) break;
  }

  return arr;
}
Time
O(n^2)
Space
O(1)
5. Test cases

Test cases

InputExpectedCovers
nums = [2, 0, 2, 1, 1, 0][0, 0, 1, 1, 2, 2]example from the docstring
nums = [0, 0, 0][0, 0, 0]every element is the same value
nums = [2, 2, 2][2, 2, 2]every element is the maximum value
nums = [0, 0, 1, 1, 2, 2][0, 0, 1, 1, 2, 2]already sorted, no swaps needed
nums = [2, 1, 0][0, 1, 2]worst case, fully reverse sorted
nums = [1][1]smallest valid input, a single element
nums = [1, 0, 2, 0, 1, 2][0, 0, 1, 1, 2, 2]values interleaved with no existing order

Keep reading

TopicDescription
Bubble SortRepeatedly swap neighboring out-of-order elements until the whole list is sorted, simple but slow on large lists.
Implement Bubble SortSort an array by repeatedly comparing and swapping adjacent out-of-order pairs.
Count Bubble Sort SwapsSort with bubble sort and return the total number of adjacent swaps performed.
Bubble Sort Pass CountReturn how many passes an early-exit bubble sort takes to finish sorting.
Minimum Adjacent Swaps to Sort an ArrayFind the minimum number of adjacent swaps needed to sort an array of distinct integers.
Sort a Nearly Sorted Array (Elements at Most K Away)Sort an array where every element is at most k positions from its sorted position.