/ bubble sort

Sorting Algorithms: Bubble Sort using javascript

Bubble sort is one of the least efficient sorting algorithms but it is also the simplest to understand. This post covers the essentials of bubble sort using JavaScript. We will use a simple array to demonstrate the concepts of Bubble Sort before getting into code.

Concept:

In Bubble Sort, we start from the first element in the array and compare this with the adjacent element in the array. If the first element is greater than the second, we swap their positions. If not, we compare the second element with the third element and so on. At the end of Pass 1, we will have the highest number at the last position of the array. Following images demonstrate Pass 1 of bubble sort.

Step 1: Initial Array

Initial Array

Step 2: Compare first element with second

Step 1 - Compare 1st with 2nd element

Compare the first element with second element of the array. If the element is larger, swap the positions. In this case, number 4 is greater than 3. We should swap the positions.

Step3: Compare second element with third

Compare 2nd with 3rd

Compare second element with third element. This time, 4 < 5. We will not swap the numbers.

Step 4: Compare third element with fourth

Compare third with fourth

Again, 5 > 1. So, we swap the positions.

Step 5: Compare fourth element with fifth

Compare fourth with fifth

Here 5 < 7. Don’t swap the numbers

Step 6: Compare fifth element with sixth

Compare fith with sixth

7 > 6. Swap 6 and 7.

Step 7: Compare sixth element with seventh

Compare sixth and seventh

7 < 8. Don’t swap

Step 8: Compare seventh element with eighth

Compare seventh with eighth

8 > 2. Swap the numbers.

After swapping the numbers, Number 8 (Largest number in the array) is positioned at the end of the array. This completes Pass 1 of bubble sort as below:

Pass 1
Pass 1

Once we have completed Pass 1, we repeat the compare and swap step starting from the first element of the array but till the second last element of the array. We don’t compare the last element as we know that the last element is already the largest after completion of Pass 1.

Pass 2:

Pass 2Pass 2

At the end of Pass 2, we will have the second largest number at second last position of the array.

Pass 3:

In Pass 3, we will start comparing the numbers starting at first position till the third last position of the array (Pass 1 and Pass 2 has already completed)

Pass 3Pass 3

Similarly:

Pass 4:

Pass 4Pass 4

Pass 5:

Pass 5Pass 5

and so on.

Finally, after all the passes, we will have a sorted array as follows:

Sorted ArraySorted Array

Complexity:

Let’s calculate the complexity involved in Bubble Sort algorithm using Big-O notation.

For an array of size N, it requires N steps to complete Pass 1 but it requires N-1 steps to complete Pass 2 as we don’t traverse last element. Similarly, we need N-2 steps for Pass 3 and so on.

Total number of steps required to sort an array using bubble sort is:

N + (N-1) + (N-2) + …     ≈  (N * (N-1)) / 2 (sum of N natural numbers)

For N → ∞ :

Number of steps ≈ N².

Complexity of Bubble Sort: O(N²)

Bubble Sort in Javascript

Implementing Bubble Sort is very straight-forward once the concept is clear. Following function takes an array as argument and sort the content using bubble sort.

function bubbleSort(items) { var length = items.length; for (var i = 0; i < length; i++) { //Number of passes for (var j = 0; j < (length - i - 1); j++) { //Notice that j < (length - i) //Compare the adjacent positions if(items[j] > items[j+1]) { //Swap the numbers var tmp = items[j]; //Temporary variable to hold the current number items[j] = items[j+1]; //Replace current number with adjacent number items[j+1] = tmp; //Replace adjacent number with current number } } } }

Another form of bubble sort includes starting at the end of the array and placing the smallest element first and going till the largest. So, at the end of Pass 1, smallest number will be placed at the first position. Following JavaScript code illustrates this.

function bubbleSort(items) {
	var length = items.length;
	for (var i = (length - 1); i >= 0; i--) {
		//Number of passes
		for (var j = (length - i); j > 0; j--) {
			//Compare the adjacent positions
			if (items[j] < items[j - 1]) {
				//Swap the numbers
				var tmp = items[j];
				items[j] = items[j - 1];
				items[j - 1] = tmp;
			}
		}
	}
}

Conclusion:

You would not use Bubble Sort for sorting an array in your day to day code. Instead, use items.sort() from the JavaScript inbuilt Array method. The aim of this post was to illustrate the Bubble Sort Technique. Even though bubble sort is most inefficient, it is still the most common sorting algorithm because of its simplicity.

Practice Exercise:

  1. Write a program in JavaScript to sort following list in ascending order using Bubble Sort Algorithm.
    var nums = [34, 23, 12, 45, 9, 1, 24];
  2. Sort the list present in Q1 in descending order.
  3. Sort the following array of Persons in ascending order of ‘age’ using Bubble Sort.
    var persons = [
    {
    "name": "john",
    "age": "23"
    },
    {
    "name": "harry",
    "age": "21"
    },
    {
    "name": "jack",
    "age": "25"
    }
    ];