How to Do a Bubble Sort in JavaScript

How to Do a Bubble Sort in JavaScript

In this article, you'll learn how to implement bubble sorting in JavaScript. We’ll briefly discuss different types of sorting algorithms, and we’ll specifically look at how a bubble sort works in JavaScript.

Sorting is one of the most important concepts in the field of programming, as it allows you to arrange and locate elements much more easily and efficiently. Of course, JavaScript has a built-in sorting function for arrays, and you will use that most of the time, but it is good to now how the classic sorting algorithms work anyways.

In the next section, we’ll look at a couple of popular sorting algorithms that you can implement, including bubble sort. Finally, we’ll implement a real-world example to demonstrate how to implement a bubble sort in JavaScript.

Different Types of Sorting Algorithms

When it comes to sorting algorithms, there are a lot of choices. Let’s have a quick look at some of the most important sorting algorithms:

• bubble sort
• merge sort
• quick sort
• insertion sort

Different sorting algorithms each have their own method of sorting the elements. They also each require different amounts of memory and time. A bubble sort is one of the simplest sorting algorithms, so it's a popular tool for teaching algorithms.

It has O(n²) complexity in the worst case, but O(n) in the best case. That means if the array to be sorted has n items, the bubble sort algorithm needs a number of steps proportional to n² to execute. 

algorithm	average time complexity	average space complexity
bubble sort	O(n2)	O(1)
insertion sort	O(n2)	O(1)
quick sort	O(n log n)	O(n log n)
merge sort	O(n log n)	O(n)

How a Bubble Sort Works

In this section, we’ll see how exactly a bubble sort works.

Let’s assume that you have a list of numbers which you want to arrange in ascending order. In a bubble sort, the adjacent elements in a list are compared and positions of the elements are swapped if the first element is greater than the second element. This process is repeated until all the elements are in correct order. Elements are bubbled up in a list during the whole process, and that’s why it’s called a bubble sort.

Usually, if a list contains n elements, you need to perform n passes through the entire array in order to put it in order.

Let’s have a look at the following list:

9,3,10,2,15

We’ll try to understand what happens in the first iteration.

In each iteration, the algorithm will start by comparing elements from the beginning of the list. First, it’ll compare the first and second elements, and since the first element is greater than the second element, they are swapped as shown in the following list.

3,9,10,2,15

Next, it’ll compare the second and third element in the same way. In our example, they are already in order so there’s no need to swap. At the end of the first pass through, the array will look like this:

3,9,2,10,15

Now, the algorithm repeats the same process again in the second iteration. And as we said, if a list contains n number of elements, you will generally need to perform n iterations to sort the whole list—comparing n elements each time for an overall time cost of O(n²). However, if any iteration finds the array already in order—meaning no swaps were required—the algorithm will terminate. So, if the array is already in order, the algorithm will terminate after one iteration, making n comparisons, with an overall complexity of O(n).

As shown in the following snippet, the list is in the correct order after three iterations.

Iteration 1: [9,3,10,2,15] => [3,9,10,2,15] => [3,9,10,2,15] => [3,9,2,10,15] => [3,9,2,10,15]
Iteration 2: [3,9,2,10,15] => [3,9,2,10,15] => [3,2,9,10,15] => [3,2,9,10,15] => [3,2,9,10,15]
Iteration 3: [3,2,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15] => [2,3,9,10,15]

So that’s how a bubble sort works. In the next section, we’ll see how you can implement a bubble sort in your JavaScript projects.

How to Implement a Bubble Sort in JavaScript

In this section, we’ll build a real-world example to demonstrate how you can implement a bubble sort in JavaScript.

Let’s have a look at the following example.

As you can see, we’ve implemented the bubbleSort helper function, which helps you to perform array sorting. In the first argument of the the bubbleSort function, you need to pass an array, and it’ll sort it and return the sorted array as a response.

Let’s quickly go through the implementation of the bubbleSort function. 

Firstly, we measure the length of the input array and assign it to the n variable. It’ll be used to decide the number of iterations that we’re going to perform to sort the input array.

Moving ahead, we’ve used the for loop to perform the n iterations, where n is the length of the array. For each iteration, we’ve defined another for loop, which will compare every pair of adjacent array elements, and swap them if the first element is greater than the second element. After each iteration, we’ll check the value of the swapped variable, and if it hasn’t changed from false to true, it means that no swapping was done at all in the last iteration, and thus the input array is now completely sorted. On the other hand, if the swapped variable has changed from false to true, it means that swapping was done at least once in the last iteration, and we’ll proceed for the next iteration. After all iterations, the input array is completely sorted, and we’ll return it.

So that’s how you can implement a bubble sort in JavaScript!

Conclusion

Today, we discussed how you can implement a bubble sort in JavaScript. This is a great place to start learning sort algorithms, but don't stop here! Bubble sort is one of the least efficient sort algorithms, try learning quick sort or merge sort to understand how an efficient algorithm works.