Bubble Sort

Bubble sort is one of the simplest sorting methods. In case you are wondering where this odd name for a sorting technique came from-- lighter bubbles in water always float to the top. Heavy objects sink to the bottom.

We use a similar idea when sorting items in an array: "bubble down" heavier or bigger keys. Alternatively, we can bubble up lighter keys.

Let's take a look at this technique that bubbles down all the heavier keys to the end of the array. Bubble sort divides the entire array into a sorted half and an unsorted half. It works by using the following principle:

1. Maintain an unsorted left sub-array and a sorted right sub-array.
2. Bubble down the heaviest item in the unsorted half to the right sub-array.

How do you bubble down the heaviest key? One way of doing it is by comparing consecutive keys and swapping if left key is greater than the right key. Here is the complete pseudo-code:

1Routine: bubbleSort
2Input: Unsorted array X of size n
3
41. sorted = false
52. totalSorted = 0
63. while (totalSorted < (n-1) and !sorted)
7    {
8        a.sorted = true     // will remain true if no swaps are made
9        b. for i=1 .. (n-1 - totalSorted)
10        {
11            i. if X[i-1] > X[i]
12                {     swap(X[i-1],X[i])
13                      sorted = false
14                }
15        }
16        c. totalSorted++
17    }

xxxxxxxxxx

function bubbleSort(arr) {

  for (let i = 0; i < arr.length; i++) {

    for (let j = 0; j < arr.length - i - 1; j++) {

      if (arr[j] > arr[j + 1]) {

        // Swap here

        let temp = arr[j];

        arr[j] = arr[j + 1];

        arr[j + 1] = temp;

      }

    }

  }

​

  console.log(arr);

}

​

bubbleSort([3, 2, 1]);