Trusted answers to developer questions

Abel Lifaefi Mbula

In this shot, we will learn about the sorting algorithm called *bubble sort* and how to implement it in JavaScript.

Let’s get started.

First thing first, what is a bubble sort?

The **bubble sort** is a simple sorting algorithm that continues to swap adjacent values, if they are in the incorrect order, until all the values are sorted.

Simply speaking, bubble sort compares all the elements one by one and sorts them based on their values.

For example, if you are given a list of integers to sort in ascending order, we could use bubble sort and begin by comparing the first item of the list with the next one. Ff the first item is greater than the second one, we can swap both of them. We will then compare the second item with the third one and continue like this until we reach the last item.

Let’s consider a sample array with the following expected output:

- array:
`[4, 3, 5, 9, 1]`

- output:
`[1, 3, 4, 5, 9]`

Here is how the bubble sort will sort this sample array step-by-step. Items in **bold** are those that are being compared.

**First iteration**:

[**4**, **3**, 5, 9, 1] --> [3, 4, 5, 9, 1], 4 > 3 so swap

[3, **4**, **5**, 9, 1] --> [3, 4, 5, 9, 1], 4 < 5 so no swapping

[3, 4, **5**, **9**, 1] --> [3, 4, 5, 9, 1], 5 < 9 so no swapping

[3, 4, 5, **9**, **1**] --> [3, 4, 5, 1, 9], 9 < 1 so swap

**Second iteration**

[**3**, **4**, 5, 1, 9] --> [3, 4, 5, 1, 9], 3 < 4 so no swapping

[3, **4**, **5**, 1, 9] --> [3, 4, 5, 1, 9], 4 < 5 so no swapping

[3, 4, **5**, **1**, 9] --> [3, 4, 1, 5, 9], 5 > 1 so swap

[3, 4, 1, **5**, **9**] --> [3, 4, 1, 5, 9], 5 < 9 so no swapping

**Third iteration**

[**3**, **4**, 1, 5, 9] --> [3, 4, 1, 5, 9], 3 < 4 so no swapping

[3, **4**, **1**, 5, 9] --> [3, 1, 4, 5, 9], 4 > 1 so swap

[3, 1, **4**, **5**, 9] --> [3, 1, 4, 5, 9], 4 < 5 so no swapping

[3, 1, 4, **5**, **9**] --> [3, 1, 4, 5, 9], 5 < 9 so no swapping

**Fourth iteration**

[**3**, **1**, 4, 5, 9] --> [1, 3, 4, 5, 9], 3 > 1 so swap

[1, **3**, **4**, 5, 9] --> [1, 3, 4, 5, 9], 3 < 4 so no swapping

[1, 3, **4**, **5**, 9] --> [1, 3, 4, 5, 9], 4 < 5 so no swapping

[1, 3, 4, **5**, **9**] --> [1, 3, 4, 5, 9], 5 < 9 so no swapping

**Fifth iteration**

[**1**, **3**, 4, 5, 9] --> [1, 3, 4, 5, 9], 1 < 3 so no swapping

[1, **3**, **4**, 5, 9] --> [1, 3, 4, 5, 9], 3 < 4 so no swapping

[1, 3, **4**, **5**, 9] --> [1, 3, 4, 5, 9], 4 < 5 so no swapping

[1, 3, 4, **5**, **9**] --> [1, 3, 4, 5, 9], 5 < 9 so no swapping

As you can see in the $4^{th}$ iteration, the array is already sorted, but the algorithm does not know if it is complete. The algorithm needs one **whole** pass without any **swap** to know it is sorted. You will see the reason in the $5^{th}$ iteration.

I always see pseudocode as a good way to write my thoughts on an algorithm in plain English before writing it in a real programming language. This is what I call the pseudocode notation (example below):

```
function bubbleSort(arr)
Set isSwapped to true
WHILE isSwapped = true
Reset isSwapped to false
FOR each item in the arr
IF current item > next item
swap items
Reset isSwapped to true
ENDIF
ENDFOR
ENDWHILE
RETURN arr
```

You can read a post I wrote about pseudocode here.

Let’s translate our pseudocode into JavaScript.

function bubbleSort(arr) { let isSwapped = true while(isSwapped) { isSwapped = false arr.forEach((item, index) => { if(item > arr[index + 1]) { arr[index] = arr[index + 1] arr[index + 1] = item isSwapped = true } }) return arr } } let arr = [4, 3, 5, 9, 1]; arr = bubbleSort(arr); console.log(arr);

Nothing tricky here – I simply used a `while`

loop and preferd to use `forEach`

to iterate over the passed array.

To end our journey, let me say just one word about the performance of this algorithm.

Bubble sort is a very simple sorting algorithm, but it is too slow. For this reason, you’ll almost never find or use it in the real world. In fact, it is mostly used for educational purposes.

- Worst Case Time Complexity, aka Big-O: $O(n^2)$
- Best Case Time Complexity, aka Big-omega: $O(n)$
- Average Time Complexity, aka Big-theta: $O(n^2)$
- Space Complexity: $O(1)$

RELATED TAGS

javascript

communitycreator

CONTRIBUTOR

Abel Lifaefi Mbula

RELATED COURSES

View all Courses

Keep Exploring

Related Courses