[Elementary Sorting Algotithms] Bubble sort

What is sorting?

Sorting is the process of rearranging the items in a collection (e.g. an array) so that the items are in some kind of order.

 

Examples

• Sorting numbers
• Sorting names alphabetically
• Sorting movies based on release year
• Sorting movies based on revenue

Why do we need to learn this?

• Sorting is an incredibly common task, so it's good to know how it works
• There are many ways and there are pros and cons
• Sorting Algorithms Animations

 

Elementary sort 

• Bubble sort
• Selection sort
• Insertion sort

 

Built-in Javascript sort

.sort()

works with string

not working with number

 

• The built-in sort method accepts an optional comparator function
• You can use this comparator function to tell JS how you want it to sort
• The comparator looks at pairs of elements(a and b), determines their sort order based on the return value
  • if it returns a negative number, a should come before b
  • if it returns a positive number, a should come after b
  • if it returns 0, a and b are the same as far as the sort is concerned

function numberCompare(num1, num2){
 return num1-num2;
 }
 
 [6,4,15,10].sort(numberCompare)

 

Big O of Sorting Algorithms

Algorithm	Time complexity (Best)	Time complexity (Average)	Time complexity (Worst)	Space complexity
Bubble sort	O(n)	O(n^2)	O(n^2)	O(1)
Insertion sort	O(n)	O(n^2)	O(n^2)	O(1)
Selection sort	O(n^2)	O(n^2)	O(n^2)	O(1)

toptal | Sorting Algorithms Animations

visualgo | Sorting

Recap

• sorting is fundamental
• bubble sort, selection sort, and insertion sort are all roughly equivalent
• all have average time complexities that are quadratic
• we can do better but we need more complex algorithms

 

Bubble Sort

Not efficient, not commonly used. but it's fun one and and you can optimize it.

Visualso | Bubble sort

 

A sorting algorithm where the largest values bubble up to the top

Swapping is the key!

 

Pseudocode

• Start looping from with a variable called i the end of the array towards the beginning
• Start an inner loop with a variable called j from the beginning until i-1
• If arr[j] is greater than arr[j+1], swap those two values
• Return the sorted array

 

Less optimized

이미 가장 큰 숫자를 계속 대조함

끝을 정해주지 않았기 때문에 undefined와 비교하게 됨

 

Optimized

끝에서 앞으로 돌리는 반복문을 해줌

function bubbleSort(arr) {
  for (let i = arr.length; i > 0; i--) {
    //use i in the definition of j
    for (let j = 0; j < i - 1; j++) {
      //console.log(arr,arr[j],arr[j+1])
      if (arr[j] > arr[j + 1]) {
        //SWAP!
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
    //console.log("ONE PASS COMPLETE!")
  }
  return arr;
}

function bubbleSort(arr) {
  const swap = (arr, idx1, idx2) => {
    [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx2]];
  };

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

 

More optimized with noSwaps

이미 많이 sort되어 있는 경우 더 optimize할 수 있음

function bubbleSort(arr) {
  let noSwaps;
  for (let i = arr.length; i > 0; i--) {
    //use i in the definition of j
    noSwaps=true;
    for (let j = 0; j < i - 1; j++) {
      //console.log(arr,arr[j],arr[j+1])
      if (arr[j] > arr[j + 1]) {
        //SWAP!
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        noSwaps=false;
      }
    }
    //console.log("ONE PASS COMPLETE!")
    if(noSwaps) break;
  }
  return arr;
}

 

Big O

• average, worst: O(n^2)
• best: O(n)