DEV Community

Cover image for Bubble sort algorithm
CONRAD
CONRAD

Posted on

Bubble sort algorithm

The Bubble sort algorithm is a simple sorting algorithm that operates by comparing pairs of values in an array. It works by iterating through the array and comparing adjacent values, swapping them if the value on the left is greater than the value on the right. This process is repeated until there are no more values that are greater than the highest value in the array, resulting in a sorted list/array in ascending order.

While Bubble sort is a straightforward algorithm, it can be slow and inefficient for large arrays. Despite its limitations, it is still a useful algorithm to understand as it forms the foundation for more complex sorting algorithms.

In summary, the Bubble sort algorithm compares pairs of values and swaps the greatest with the least until the array is sorted in ascending order.

so the steps are simple:

  1. nested loop to run through input array, using 2 variables (i and j). such that 0≤i≤(n-1) and 0≤j≤(n-i-1)
  2. if arr[j] is greater than arr[j+1] then swap the adjacent value else so on.
  3. return sorted array.

Below is the solution in javascript.

const swap = (arr, pos1, pos2) =>  {
    //swap pos2 val with pos1 val
    let temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

const bubbleSort = (arr = []) => {
    let len = arr.length;

    for(let i=0; i<len; i++) {
        for(let j=0; j<(len - i - 1); j++ ) {  

            //swap arrayValue with its adjacent if its greater than it.
            if(arr[j] > arr[j+1]) {
                swap(arr, j, j+1); 
            }
        }
    }
    return arr;
}
Enter fullscreen mode Exit fullscreen mode

The Best case scenario is when the input array is sorted in ascending order, worst case scenario is when the input array is sorted in descending order.
Time complexity for Best case O(n);
Time complexity for Worst case O(n^2);

Worst case scenario analysis:
If the input array is in descending order, that means that many iterations/passes will be required to swap elements
total number of iterations on an input array (n-1)

At iteration 1: Number of comparisons = (n-1)
Number of swaps = (n-1)

At iteration 2: Number of comparisons = (n-2)
Number of swaps = (n-2)

At iteration 3: Number of comparisons = (n-3)
Number of swaps = (n-3) .... and so on
= (n-1) + (n-2) + (n-3) + . . . 2 + 1
= (n-1)*(n-1+1)/2 { using sum of n natural Number formula }
= n(n-1)/2

= n^2
therefore Total number of swaps = Total number of comparisons
Worst case scenario: O(n^2)

Input:
[6,4,1]
Output:
[1, 4, 6]
Enter fullscreen mode Exit fullscreen mode

Bubblesort is relatively easy to implement but due to its time complexity of O(n^2) it can be very slow for large datasets.

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

👋 Kindness is contagious

Discover a treasure trove of wisdom within this insightful piece, highly respected in the nurturing DEV Community enviroment. Developers, whether novice or expert, are encouraged to participate and add to our shared knowledge basin.

A simple "thank you" can illuminate someone's day. Express your appreciation in the comments section!

On DEV, sharing ideas smoothens our journey and strengthens our community ties. Learn something useful? Offering a quick thanks to the author is deeply appreciated.

Okay