Follow

# DevBerg

Follow # Understanding Bubble Sort

Rod Lu
·Jan 2, 2023·

• Simple Bubble Sort
• Optimized Bubble Sort

Bubble sort is one of the simplest algorithms to use and a nice algorithm for a beginner level to play with and learn the logic behind it.

Let's assume we have the following unordered list of integers below and we want to sort it in ascending order like below:

Unordered items
4, 1, 3, 5, 2

Ordered items
1, 2, 3, 4, 5

In Bubble Sort we scan the array from left to right checking if items are out of order by comparing them side by side items and swapping every pair of items until we reach the end of the list.

We start by comparing items starting at index 0 and 1.

[ 4 ] [ 1 ] [ 3 ] [ 5 ] [ 2 ]
First, we compare indexes 0 and 1. If the right item is smaller than the left item we simply swap values.

[ 4 ] [ 1 ] [ 3 ] [ 5 ] [ 2 ]
Then, we compare indexes 1 and 2. If the right item is smaller than the left item we simply swap values.

[ 4 ] [ 1 ] [ 3 ] [ 5 ] [ 2 ]
Next, we compare indexes 2 and 3. If the right item is smaller than the left item we simply swap values.

[ 4 ] [ 1 ] [ 3 ] [ 5 ] [ 2 ]
Lastly, we compare indexes 3 and 4. If the right item is smaller than the left item we simply swap values.

At the end of each pass the next largest item is moved to its correct position. This is why we call this algorithm Bubble Sort, because at the end of each pass the next largest item bubbles up and moves one position again and again until it reaches the last position of the array.

This means that in order to fully sort this array we need multiple iterations. To achieve our goal we need 2 for each loops:

One outer loop starting at index 0 and one inner loop starting at index 1.

The outer one loops through all items of the array. The inner one loop, always being one step ahead, is used to compare every two items of the array on each iteration.

### Simple Bubble Sort

``````<script>
let ar = [4, 1, 3, 5, 2];
console.log("Original Array");
console.log(ar)
console.log('Outer Loop');
for (let i = 0; i < ar.length; i++) {
console.log('`i` is ' + i);
console.log('Inner Loop');
for (let j = 1; j <  ar.length; j++) {
if (ar[j] < ar[j-1]) {
// Swap values here
let temp = ar[j];
ar[j] = ar[j-1];
ar[j-1] = temp;
}
console.log('`j` is ' + j+ ":" + " `ar `is ["+ ar+"]");
}
console.log(ar);
}
console.log("Array After Sorting");
console.log(ar);
</script>
``````

Output:

``````Original Array
[4, 1, 3, 5, 2]
Outer Loop
i is 0
Inner Loop:
j is 1: ar is [1,4,3,5,2]
j is 2: ar is [1,3,4,5,2]
j is 3: ar is [1,3,4,5,2]
j is 4: ar is [1,3,4,2,5]
[1,3,4,2,5]
Outer Loop:
i is 1
Inner Loop:
j is 1: ar is [1,3,4,2,5]
j is 2: ar is [1,3,4,2,5]
j is 3: ar is [1,3,2,4,5]
j is 4: ar is [1,2,3,4,5]
[1,2,3,4,5]
Outer Loop:
i is 2
Inner Loop:
j is 1: ar is [1,2,3,4,5]
j is 2: ar is [1,2,3,4,5]
j is 3: ar is [1,2,3,4,5]
j is 4: ar is [1,2,3,4,5]
[1,2,3,4,5]
Outer Loop:
i is 3
Inner Loop
j is 1: ar is [1,2,3,4,5]
j is 2: ar is [1,2,3,4,5]
j is 3: ar is [1,2,3,4,5]
j is 4: ar is [1,2,3,4,5]
[1,2,3,4,5]
Outer Loop:
i is 4
Inner Loop:
j is 1: ar is [1,2,3,4,5]
j is 2: ar is [1,2,3,4,5]
j is 3: ar is [1,2,3,4,5]
j is 4: ar is [1,2,3,4,5]
[1,2,3,4,5]
Array After Sorting:
[1,2,3,4,5]
``````

The outer loop works as a slider making sure you compare all items in the array. In order to compare the two items at index "j" on the inner loop we start at index j=1.

Now, there are some issues in regards to efficiency with this Bubble Sort implementation because we assume that we need "n" iterations to fully sort this array, but we don't consider the scenario where the array might be already sorted or might be partially sorted when in reality we need fewer iterations to sort it more efficiently.

### Optimized Bubble Sort

In the previous scenario we could add two extra optimizations to improve performance. One strategy is to use a isSorted flag to check if the array is already sorted and exit the loop as soon as we find that the array is already sorted.

Because we go through the entire array comparing every two items another optimization strategy is to skip the last sorted items in the array on the second loop.

Finally, since we know that the next largest item always bubbles up to end of the array, then we don't need to compare all the items in the array because some items might be already in the right position. Therefore we only need to compare items that are not in the correct position.

Here is a more efficient Bubble sort version:

``````<script>
let ar = [4, 1, 3, 5, 2];
console.log("Original Array");
console.log(ar)
console.log("Array over Iterations");
let isSorted;
for (let i = 0; i < ar.length; i++) {
isSorted = true;
console.log(ar.length-i);
for (let j = 1; j <  ar.length-i; j++) {
if (ar[j] < ar[j-1]) {
let temp = ar[j];
ar[j] = ar[j-1];
ar[j-1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
console.log(ar);
}
console.log("Array After Sorting");
console.log(ar);
</script>
``````