Bubble Sort

Bubble Sort is a simple sorting algorithm that works by repeatedly comparing two adjacent elements in an array and swapping them if they are in the wrong order.

Just like bubbles rise to the top in water, in Bubble Sort the biggest numbers slowly move to the end of the list with each round. That’s why it’s called Bubble Sort.

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)

1. Starting from the first index, compare the first and the second elements.

2. If the first element is greater than the second element, they are swapped.

3. Now, compare the second and the third elements. Swap them if they are not in order.

4. The above process goes on until the last element.

2. Remaining Iteration

The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

In each iteration, the comparison takes place up to the last unsorted element.

The array is sorted when all the unsorted elements are placed at their correct positions.

Bubble Sort Algorithm

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
end bubbleSort

Bubble sort code :

function bubbleSort(arr) {

  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }

  return arr;
}

console.log(bubbleSort([-4, 34, 2, 13, -8]));

In the above algorithm, all the comparisons are made even if the array is already sorted.

This increases the execution time.

To solve this, we can introduce an extra variable swapped. The value of swapped is set true if there occurs swapping of elements. Otherwise, it is set false.

After an iteration, if there is no swapping, the value of swapped will be false. This means elements are already sorted and there is no need to perform further iterations.

This will reduce the execution time and helps to optimize the bubble sort.

Algorithm for optimized bubble sort is

bubbleSort(array)
  for i <- 1 to sizeOfArray - 1
    swapped <- false
    for j <- 1 to sizeOfArray - 1 - i
      if leftElement > rightElement
        swap leftElement and rightElement
        swapped <- true
    if swapped == false
      break
end bubbleSort

Optimized bubble sort code :

function optimizedBubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let swapped = false;
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }
    if (!swapped) break;
  }

  return arr;
}

console.log(optimizedBubbleSort([-4, 34, 2, 13, -8]));

Bubble Sort Complexity

Complexity in Detail

Bubble Sort compares the adjacent elements.

Hence, the number of comparisons is nearly equals to n2

(n-1) + (n-2) + (n-3) +.....+ 1 = n(n-1)/2

Hence, Complexity: O(n2)

Also, if we observe the code, bubble sort requires two loops. Hence, the complexity is n*n = n2

1. Time Complexities

• Worst Case Complexity: O(n2) If we want to sort in ascending order and the array is in descending order then the worst case occurs.

• Best Case Complexity: O(n) If the array is already sorted, then there is no need for sorting.

• Average Case Complexity: O(n2) It occurs when the elements of the array are in jumbled order (neither ascending nor descending).

2. Space Complexity

• Space complexity is O(1) because an extra variable is used for swapping.

• In the optimized bubble sort algorithm, two extra variables are used. Hence, the space complexity will be O(2).

Bubble Sort Applications

1. Teaching and Learning: Bubble Sort is widely used to teach sorting algorithms and programming logic to beginners. It’s easy to understand and implement.

2. Small Data Sets (Games or Visualizations): Used in animations or sorting visualizers to show how sorting works step-by-step. Great for game leaderboards or quick local sorting.

3. Detecting Small Errors: If a list is almost sorted, Bubble Sort can quickly correct minor mistakes with just a few passes.

4. Embedded Systems / Microcontrollers: In low-memory environments, where simplicity is more important than speed, Bubble Sort might be used.

5. Sorting in GUI applications (like drag-and-drop): Bubble Sort can be used in simple GUI apps for live sorting small items (e.g., drag-and-drop sortable lists).