Bubble Sort Explaination

Bubble sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the entire list is sorted.

How the bubble sort algorithm works:

1. Iterate Through the List:
   • Start at the beginning of the list.
   • Compare the first two elements. If they’re in the wrong order, swap them.
2. Repeat Comparison and Swapping:
   • Move to the next pair of elements and compare them.
   • Continue this process, moving through the list, comparing adjacent elements, and swapping them if necessary.
   • After the first iteration, the largest (or smallest, depending on the sorting order) element will be at the end of the list.
3. Repeat Until Sorted:
   • Continue this process for multiple passes through the list.
   • With each pass, the next largest (or smallest) element will “bubble up” to its correct position.
4. Termination:
   • The algorithm terminates when no more swaps are needed during a pass, indicating that the list is sorted.

Here’s an example to illustrate the steps of the bubble sort algorithm:

Consider an unsorted array: [4, 7, 9, 3, 1]

Pass 1:

• Compare 4 and 7. No swap is needed. Array remains [4, 7, 9, 3, 1].
• Compare 7 and 9. No swap is needed. Array remains [4, 7, 9, 3, 1].
• Compare 9 and 3. Swap because 9 > 3. Array becomes [4, 7, 3, 9, 1].
• Compare 9 and 1. Swap because 9 > 1. Array becomes [4, 7, 3, 1, 9].

Pass 2:

• Compare 4 and 7. No swap is needed. Array remains [4, 7, 3, 1, 9].
• Compare 7 and 3. Swap because 7 > 3. Array becomes [4, 3, 7, 1, 9].
• Compare 7 and 1. Swap because 7 > 1. Array becomes [4, 3, 1, 7, 9].

Pass 3:

• Compare 4 and 3. Swap because 4 > 3. Array becomes [3, 4, 1, 7, 9].
• Compare 4 and 1. Swap because 4 > 1. Array becomes [3, 1, 4, 7, 9].

Pass 4:

• Compare 3 and 1. Swap because 3 > 1. Array becomes [1, 3, 4, 7, 9].

Bubble sort is straightforward to understand and implement but is not efficient for large datasets due to its time complexity of O(n^2), where ‘n’ is the number of elements. Other more efficient sorting algorithms like quicksort, mergesort, or heapsort are preferred for larger datasets due to their better average and worst-case time complexities.

bubble sort algorithm function

/**
 * @approach Align big digit to small digit [... <- 4 <- 7 <- 9]
 * @complexity
 * - Time complexity: O(n2); Call: Order of n square
 * - Space complexity: O(1); Call: Order of 1
 */
function bubbleSort(arr: number[]): number[] {
  let i: number = 0,
    j: number,
    temp: number;
  for (i; i < arr.length; i++) {
    for (j = 0; j < arr.length - (i + 1); j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}


const arr = [4, 7, 9, 3, 1];
console.log(bubbleSort(arr)); // [ 1, 3, 4, 7, 9 ]