Algorithms: Bubble Sort
Tags: programming, codenewbie, algorithms, computerscience
Published: 2022-09-28 17:05:52

### Introduction

Bubble sort, also known as sinking sort, is a sorting algorithm that works by looping through an array or list of elements, comparing two elements at a time and swapping them if necessary. It does this until all elements are properly ordered. Let's look at an example of this in action.

### Visualization


![Bubble sort animation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/2ota8hv6h0oibuv69e8z.gif)

The algorithm starts at the first card **[8]** and compares it to the adjacent card **[3]**, since **[8]** is greater than **[3]** so they swap positions, this is the core concept of bubble sort. 

![bubble sort animation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0jt0dqtvrogo73c1m257.gif)

The algorithm moves through the list checking two elements at a time until each element is in its proper position.

### Implementation

Let's break down this algorithm into steps before writing it out in code, so we understand how it works.

- Loop through the array or list.
- As we loop check if the current element is less than or greater than the next element.
- If the current element is greater, then swap the position of the elements, otherwise move to the next element.
- Repeat until no swapping occurs.

The above steps look like this in javascript code 


```javascript

function bubbleSort (array){
    for (var i = 0; i < array.length; i++) { // loop
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) { //comprare
       let currentIndex = array[i];
       array[i] = array[i + 1];   // swap
       array[i + 1] = currentIndex; // swap
     }
  }
  return array
}

``` 


There's a problem with the above code, it will only loop through the array once, we need a way to keep the loop going until all elements in the array are sorted and then exit the loop, for this we use a boolean to represent the current state of the array and a while loop to keep the loop going until the state of the array is sorted. In javascript code, the algorithm looks like this.


```javascript

function bubbleSort (array){
  let unsorted = true;
  while(unsorted){ 
    unsorted = false;
    for (var i = 0; i < array.length; i++) {
      if (array[i] && array[i + 1] && array[i] > array[i + 1]) {
       let currentIndex = array[i];
       array[i] = array[i + 1];
       array[i + 1] = currentIndex;
       unsorted = true;
     }
    }
  }
  return array
}


``` 

In the above function, we initialize a variable called unsorted and set the value to ***true***, while unsorted remains ***true*** we shall keep looping through the array, when we enter the while loop we assume that we will find the array sorted so we set unsorted to ***false*** if the array is not sorted, which we will know when a swap occurs we set unsorted to true and loop through the array again. Only when a swap does not occur and unsorted remains false till the end of the for loop do we end the function because that means the array is sorted.

### Time Complexity of Bubble Sort

Bubble sort has a worst and average complexity of **O(n<sup>2</sup>)**, compared to other sorting algorithms, bubble sort ranks very low in efficiency and it is recommended that programmers do not use it when solving real-world problems.

### Conclusion.

Bubble sort is meant to be an educational tool to introduce newbie programmers to the concept of algorithms as it is easy to understand and implement.