bubble-sort-async-algos-day-4.md

Bubble Sort 🛁

---

Interviewer Prompt

Write a function that takes in an array of integers and returns a sorted version of that array. Use the Bubble sort algorithm to sort the array.

---

Setup and Examples

You may provide your interviewee with these examples if you like. I would use replt for this one.

console.log(bubbleSort([8, 5, 2, 9, 5, 6, 3])) //[2, 3, 5, 5, 6, 8, 9]
console.log(bubbleSort([8, 1, 2, 3, 4, 5, 6, 7])) //[1, 2, 3, 4, 5, 6, 7, 8]
console.log(bubbleSort([1, 2, -3, -5, -17])) //[1, 2, 3]
console.log(bubbleSort([17])) //[17]

---

Interviewer Guide

---

• Make sure your interviewee knows what bubble sort is - The idea behind bubble sort is that every pair of adjacent values is compared, and then the two values swap positions if the first value is greater than the second. This way during each pass through the array, the largest value “bubbles up” to the top, and after each pass the elements furthest to the right are in the correct order.
• There are no major edge cases to consider during this problem.
• If your partner is familiar with the naive solution (brute force) and gets to it in a timely manner have them try out refactoring using the helper function (solution 2) if they need more of a challenge, have them add the boolean used in solution 3 and discuss why (we will be touching base on this in the morning)

Visualize

• Here is an example for interviewer comprehension using [5,3,1,4,6] as the input array.
  • Iteration 1: [5,3,1,4,6] → [3,5,1,4,6] → [3,1,5,4,6] → [3,1,4,5,6] → [3,1,4,5,6]
  • Iteration 2: [3,1,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6]
  • Iteration 3: [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6] → [1,3,4,5,6]

---

Solution 1 (brute force)

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

Big O

• Time Complexity: 0(n^2)
• Space Complexity: 0(1)

---

Solution 2 (helper function "swap")

function bubbleSort(arr) {	
  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;
}

function swap(arr, i, j) {
	let temporary = arr[i];
	arr[i] = arr[j];
	arr[j] = temporary
}

Big O

• Time Complexity: 0(n^2)
• Space Complexity: 0(1)

---

Solution 3 (optimized)

function bubbleSort(arr) {
let noSwapsHappened;
  for(let i = arr.length; i > 0; i--){
    noSwapsHappened = true;
    for(let j = 0; j < i - 1; j++){
       if(arr[j] > arr[j + 1]){
          let temporary = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temporary;
          noSwapsHappened = false;         
        }
      }
    if(noSwapsHappened) break;
  }
  return arr;
}

Big O

• Time Complexity: 0(n) (best case scenario)
• Space Complexity: 0(1)

---

Try it out yourself below 💁🏽‍♀️:

💻 Repl: https://repl.it/@kyvyCodes/Async-Algos-Day-4#index.js