# Sorting Algorithms: Bubble Sort using javascript

algorithms Nov 24, 2018

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 2: Compare first element with second

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 second element with third element. This time, 4 < 5. We will not swap the numbers.

#### Step 4: Compare third element with fourth

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

#### Step 5: Compare fourth element with fifth

Here 5 < 7. Don’t swap the numbers

#### Step 6: Compare fifth element with sixth

7 > 6. Swap 6 and 7.

#### Step 7: Compare sixth element with seventh

7 < 8. Don’t swap

#### Step 8: Compare seventh element 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

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 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 3

Similarly:

Pass 4

#### Pass 5:

Pass 5

and so on.

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

Sorted 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².

## 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)
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--) {
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"
}
];``````