BubbleSort Algorithm simplified

I recently attended a technical interview where I was asked to implement the bubblesort algorithm. Before now I had only a passing knowledge of it having read about it in a few tech publications without any real understanding of it.
Here I was just staring at the screen. After this moment of truth I decided to find out what the heck bubblesort algorithm really was.

The concept

The aim of this algorithm is to get an array of numbers sorted from least to greatest. This then begs the question ‘why don’t I simply use the sort() function and be done with it’. There are many ways to get an array sorted but bubblesort is implemented in a specific way and that’s what makes it bubblesort.

Let say we are given an array of numbers [ 9,3,10,6,1,2]. Using this algorithm, the idea is to loop through the entire array and compare every number with its neighbor on the right checking to see that they are in the correct order. If the number on the right is less than the number on the left we switch their positions.

Using our sample array above, we compare 9 & 3, 9 is greater than 3 so we switch their positions. We then compare 9 & 10, these are in the correct order so no need to switch. Next 10 & 6 we switch positions and 10 takes the place of 6, next 10 & 1 again we switch and finally 10 & 2 again we switch and eventually 10 bubbles to the end of the array.
After the first loop the largest number will end up at the end of the array, in this case 10.
In the next loop we will not need to compare the last number in the array as this will definitely be the largest number. What this means is that after the first loop subsequent loops each stops one position short of the last loop.

The loop is continued until all the numbers are in the correct order ie from least to greatest.

The next question is how many times will the loop run to get the array sorted. The loop will run exactly N-1 times where N is the array length.

Lets write a function called bubbleSort.

     function bubbleSort(arr){
        for(var i = arr.length; i > 0; i--){
           for(j = 0; j < i; j++){
               if(arr[j] > arr[j+1]){
                  var temp = arr[j];
                      arr[j] = arr[j+1];
                      arr[j+1] = temp;
                 }
              }
           }
          return arr;
        }

I decided to use a function so that we can immediately test our algorithm. The function takes a single argument which is an array.

In the above code you will notice that their are two nested for loops that look like they are running in opposite directions.

The outer loop determines how many times we are going to loop through our array to sort it. This will run N-1 times. If you look carefully you will notice that it starts from the arrays length and decrements it by one on every loop. This ensures the loop runs exactly N-1 times. Also this will handle the fact that the inner loop has to stop one position short every time.

The inner loop handles the comparing of each number to its neighbor on the right. using the two for loops means that each time the outer loop runs, the inner loop will run through the array comparing the numbers and switching their positions where necessary. When the outer loop runs again the inner loop runs through the array again comparing the numbers and switching their positions where necessary. Eventually all the numbers will be sorted into the correct order from least to greatest.

And thats it .