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;
}

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]

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