3:25
TypeScript
lesson by Basarat Ali Syed

Bubble sort is considered the simplest sorting algorithm to implement.

In this lesson we cover the bubble sort algorithm, how it gets its name, and how to implement it using TypeScript / JavaScript.

First, we will go ahead and create a simple sorting function that explains the concept of bubble sort. The function takes an array of numbers as an argument, and will return a sorted array of numbers. Within the function, we create a copy of the original array using slice and then we return this array.

Before returning it, we will sort it using bubble sort. Bubble sort works by looping over the input array n times. In each iteration, the goal is to bubble the highest-ranking value to the end. We loop through all the items in the array, and we simply check if the current value on the left is greater than the current value of the right.

If so, we swap the variables at the two positions. This ensures that we keep bubbling the highest value to the last position of the array. Since we're looking up the (j+1)th item, it makes obvious sense to terminate the inner loop 1 before the last index. To demonstrate this bubbling of the highest value, let's run through a simple example.

We will sort the array 4, 3, 2, 1. We expect the final result to be 1, 2, 3, 4. Within the function, we will log out the original array, and we will also log out the array whenever we do a swap.

If we run this, you can see that 4 is bubbling to the end, and then 3 is bubbling to the second last position, and finally, 2 gets bubbled to the second position. This explains the concept of bubble sort and how it gets its name.

Note that instead of always iterating n times, we can easily optimize the algorithm to terminate early. Let's duplicate the function to present a more idiomatic bubble sort implementation. We get rid of this always-in-time iterating outer loop.

We create a variable to track if any bubbling takes place. We note it down whenever we swap a variable and break out of the loop once no more swapping is needed. Finally, we wrap the whole thing in a VAR loop that will terminate if no variable bubbling happens in an iteration.

This implementation is similar to the previous one with the simple addition of early termination. This also explains the main real world use case of bubble sort, which is if you only have a few values that need to be swapped around, bubble sort can be pretty fast.

In the worst case, this whole inner FOR loop of n iterations will run 0(n) times, resulting in time complexity of 0(n)2. Since we are doing the array swaps in place, the space complexity 0(n).

## Comment Guidelines

Member comments are a way for PRO Members to communicate, interact, and ask questions about a lesson.

## Commenting Guidelines

Here are some basic guidelines for commenting on egghead.io.

## Be on-topic

Comments are for discussing a lesson. If you're having a general issue with the website functionality, please contact click here.

## Avoid meta-discussion

Is your comment resembles:

It will likely be deleted as "meta".

## Code problem?

Should be accompanied by code! JSFiddle, Plunker, CodePen, etc all provide a way to share code and discuss it in context.

## Details and Context

Vague question? Vague answer. Any details and context you can provide will lure more interesting answers!

egghead.io comment guidelines

Bubble sort is considered the simplest sorting algorithm to implement.

In this lesson we cover the bubble sort algorithm, how it gets its name, and how to implement it using TypeScript / JavaScript.

Hi, Nice tutorial. Could you recommend a book, video or article explaining about the basics of time complexity?