Bubble Sort

ℹ️ Sorting algorithm that compares every adjacent pair of values and swaps their position if the first value is greater than another. Complexity O(n²)

Description
The bubble sort algorithm runs in O(n²) time, making it an inefficient algorithm for a larger list.
The idea behind the bubble sort is that every adjacent pair of values is repeatedly compared, and then these values swap their positions if the first value is greater than the second value. This way during each pass through the array, the largest value “bubbles up” to the top.
Example
Let's imagine that we need to sort the following array using bubble sorting: [7, 1, 4, 3, 8]. Here is the list of the steps that bubble sorting will do to sort this array:
1.[7, 1, 4, 3, 8] -> [1, 7, 4, 3, 8]
2.[1, 7, 4, 3, 8] -> [1, 4, 7, 3, 8]
3.[1, 4, 7, 3, 8] -> [1, 4, 3, 7, 8]
4.[1, 4, 3, 7, 8] -> [1, 4, 3, 7, 8]
Second pass:
1.[1, 4, 3, 7, 8] -> [1, 4, 3, 7, 8]
2.[1, 4, 3, 7, 8] -> [1, 3, 4, 7, 8]
3.[1, 3, 4, 7, 8] -> [1, 3, 4, 7, 8]
4.[1, 3, 4, 7, 8] -> [1, 3, 4, 7, 8]
Now, our array is already sorted, but the algorithm doesn't know about it. The algorithm still needs one whole pass to end its sorting.
Third pass:
1.[1, 4, 3, 7, 8] -> [1, 4, 3, 7, 8]
2.[1, 3, 4, 7, 8] -> [1, 3, 4, 7, 8]
3.[1, 3, 4, 7, 8] -> [1, 3, 4, 7, 8]
4.[1, 3, 4, 7, 8] -> [1, 3, 4, 7, 8]
Code implementation
Here is one of the possible ways to implement bubble sorting:
1
function bubbleSort(inputArr) {
2
  const arr = [...inputArr];
3
​
4
  for (let i = 0; i < arr.length - 1; i++) {
5
    for (let j = 0; j < arr.length - 1 - i; j++) {
6
      if (arr[j] > arr[j + 1]) {
7
        // ⬇ Swap two elements using Destruturing assignment
8
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
9
      }
10
    }
11
  }
12
​
13
  return arr;
14
}
Copied!
Even if an array is sorted the function always runs O(n²) time. It can be optimized if the inner loop didn't make any swap during its execution.
1
function bubbleSort(inputArr) {
2
  const arr = [...inputArr];
3
  let swapped = false;
4
​
5
  for (let i = 0; i < arr.length - 1; i++) {
6
    swapped = false;
7
    for (let j = 0; j < arr.length - 1 - i; j++) {
8
      if (arr[j] > arr[j + 1]) {
9
        // ⬇ Swap two elements using Destruturing assignment
10
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
11
        swapped = true;
12
      }
13
    }
14
​
15
    // Break our loop if during inner loop execution there was no swaps
16
    if (!swapped) {
17
      break;
18
    }
19
  }
20
​
21
  return arr;
22
}
Copied!
This time if our inputArr is already sorted complexity will be O(n).
Complexity
1.Worst and Avg. Time Complexity: O(n²)
2.Best Case Time Complexity: O(n). Happens only when an array is already sorted.

Computer Science - Previous

Algorithms

Next - Computer Science

Data Structures

Last modified 1yr ago

Copy link

Contents