Bubble sort implementation idea

Bubble sort algorithm is less efficient than other sorting algorithms, but in concept it is the simplest sorting algorithm

Ideas:

  1. Compare adjacent numbers in turn and swap if the previous one is larger than the next. That means decimals in front and large numbers in back.
  2. The second and third numbers are then compared, with the decimal first and the larger number next, and so on, scrolling the largest number to the end.
  3. Start the second run and move the second largest number to the second to last
  4. And so on…..

And then it takes n minus 1 to sort it.

Reference animation:

Code implementation

class ArrayList {
  array = []
  // Used to insert data
  insert(item) {
    this.array.push(item)
  }
  swap(m,n) {
    let temp = this.array[m]
    this.array[m] = this.array[n]
    this.array[n] = temp
  }

 // Bubble sort (core code here)
  bubblesSort() {
    if (this.array === null || this.array.length < 2) { return }
    // We need length-1. And the reason is if it's the last number, it's a little bit buggy, because there's no last number plus 1
    // We can also interpret length-1 as the number of comparisons
    for (let j = this.array.length - 1; j >= 0; j--) {
      for (let i = 0; i < j; i++) {
        if (this.array[i] > this.array[i + 1]) {
          this.swap(i, i + 1)}}}}let list = new ArrayList()
list.insert(12)
list.insert(2)
list.insert(45)
list.insert(123)
list.insert(481)
list.insert(56)
console.log(list.array);   // [12, 2, 45, 123, 481, 56]


// Call bubble sort
list.bubblesSort()
console.log(list.array);  // [2, 12, 45, 56, 123, 481]
Copy the code

Efficiency of bubble sort

The number of comparisons for bubble sort (assuming that each comparison requires swapping) :

  • According to the code, there are six numbers
  • Six comparisons were made in the first cycle, five in the second, and four in the third….. Until the last trip to make a comparison
  • For six numbers, this is 6+5+4+3+2+1 times
  • So for n numbers it is: (n-1) + (n-2) + (n-3) +….. + 1 = n * (n-1) / 2

By big O notation, it’s O(N ^ 2).

Since only each comparison requires swapping, the approximate average time complexity is O(N²).