Bubble Sort

Sotring 

is the process of rearranging the itmes in a collection so that the items are in some kind of order.

 

• it is common task.
• may different ways to sort thing and
  each has own defferent pros and cons.

---

Built-In JavaScript Sorting

 

it always doesn't work how we expect it should

 

JavaScript Sort() method takes evety item that array is converted to a string

and then the Unicode value of that is taken and then they're sorted.

developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Array.prototype.sort() - JavaScript | MDN

 

we can actually specify how it should sort, what property it should sort, what to compare.

function numberCompare(num1, num2) {
  return num2 - num1;
}

[ 6, 4, 15, 10].sort(numberCompare);

function compareByLen(str1, str2) {
  return str1.length = str2.length;
}

["Steele", "Colt", "Data Structures", "Algorithms"].sort(compareByLen);

---

Bubble Sort

 

the largest values bubble up to the top one at a time.

not that efficient and not commonly used algorithm.

 

visualgo.net

visualgo.net/en/sorting

 

Swapping is really important.

swap. if something is larger and compare it to the next one.

 

//ES5
function swap(arr, idx1, idx2) {
  var temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

//ES2015
const swap = (arr, idx1, idx2) =>{
  [arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]];
}

 

• start looping from the end of the array towords the beggining with a variable called i
• start the inner loop with a variable called j from the beginning until i-1
• if arr[j] is greater than arr[j+1], swap
• return the sorted array

// UNOPTIMIZED VERSION OF BUBBLE SORT
function bubbleSort(arr){
  for(var i = arr.length; i > 0; i--){
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;         
      }
    }
  }
  return arr;
}

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

  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;
}

bubbleSort([8,1,2,3,4,5,6,7]);

 

What if the array is almost sorted?

check last time through did it make any swaps. if not, sorting is completed

 

// UNOPTIMIZED with noSwaps
function bubbleSort(arr){
  let noSwaps;
  for(var i = arr.length; i > 0; i--){
    noSwaps = true;
    for(var j = 0; j < i - 1; j++){
      console.log(arr, arr[j], arr[j+1]);
      if(arr[j] > arr[j+1]){
        var temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;    
        noSwaps = false
      }
    }
    if(noSwaps) break;
  }
  return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);

 

BIG O Complexity

in general,  n^

if it is nearly sorted, it is linear time  O(n)