Bubble Sort

easyarrayssorting

Given a list of integers nums, return a new list with the same values arranged from smallest to largest.

Use only one operation to move values around: exchanging two neighbours. Walk the list repeatedly, and whenever a value is bigger than the one right after it, swap them. After each walk the largest remaining value has drifted to the end of the unsorted part.

If a full walk makes no swaps at all, the list is already in order and you can stop early.

Constraints

1 ≤ nums.length ≤ 20
0 ≤ nums[i] ≤ 1000
Values may repeat.

Example

nums   = [6, 2, 9, 4]
result = [2, 4, 6, 9]

The first walk swaps 6 and 2, leaves 6 and 9 alone, then swaps 9 and 4, so 9 settles at the end. The second walk swaps 6 and 4. The third walk makes no swaps, so the sort is done.

nums = [5,1,4,2,8,3]expected [1,2,3,4,5,8]

Loading 3D view…

Unsorted input

step 1 / 108

Solution

TypeScript · line 1

function bubbleSort(nums: number[]): number[] {
  const a = [...nums];
  for (let end = a.length - 1; end > 0; end--) {
    let swapped = false;
    for (let i = 0; i < end; i++) {
      if (a[i] > a[i + 1]) {
        [a[i], a[i + 1]] = [a[i + 1], a[i]];
        swapped = true;
      }
    }
    if (!swapped) {
      break;
    }
  }
  return a;
}