Algorithms Practice Lesson 2 of 4

Bubble sort

Bubble sort is the first sorting algorithm most people meet, and it is worth writing once by hand. The idea is simple: walk the array comparing each value with its neighbour, and swap the two whenever they are out of order. One full pass pushes the largest value all the way to the end - it "bubbles" up. Do enough passes and the whole array is sorted.

There is one trap here that has nothing to do with sorting: mutation. If you sort the array you were handed, every other part of the program holding that same array sees it change underneath them. So make a copy first and sort the copy, leaving the caller's array exactly as it was.

Your task: write bubbleSort(input) that returns a new array with the numbers sorted in ascending order. The array you were given must be unchanged afterwards.

You'll practice:

Swapping neighbouring elements until an array is ordered
Copying an input so you never mutate the caller's data

// Return a NEW array with input's numbers sorted in ascending order.
// Do not modify the input array itself.
function bubbleSort(input) {
  // your code here
  return [];
}