September 10, 2018 · Algorithms ·

Sorting algorithms explained

Today we are going to go deeper into sorting algorithms to see the number of times they run to complete their cycle and also explore stability.

What is an Algorithm?
A process or set of rules to be followed in calculations or a set of problems. - solving operations, especially by a computer.

For this exercise, we are going to compare Sorting algorithms.

Bubble sort
This one is easy to understand, and that's why bubble sort is recommended for beginners.

For bubble sort algorithm we use do/while loop (probably you will never use it in production because it is not effective compared to other solutions.

Gist example

let numbers = [10,5,3,8,2,6,4,7,9,1];
// lets sort it with bubble sort, first we create a function
const swapper = (numbers) => {
// to acumulate number of iterations
var iterations = 0;
  do {
    // if swapping is set to false, this will be the last time do run
    var swapped = false;
    // lets use i to add logic to our sorting algorithm 
    for (let i = 0; i < numbers.length; i++) {
      // we want to sort from less than greater numbers so ->
      if (numbers[i] > numbers[i+1]) { // 10 > 8 then
        // we save our first number in an acumulator variable
        var temp = numbers[i]; // 10
        // swap the first number for the secnd
        numbers[i] = numbers[i+1]; // change 10 for 8 in first loop
       // swap second number for first number
        numbers[i+1] = temp; // change 8 for 10 in first loop
        // it swapped, lets do other iteration
        swapped = true;
        console.log(numbers);
        // we want to know the number of iterations used to solve the sorting
        console.log("iterations: "+ iterations++);
      }
    }
  } while (swapped);
}
swapper(numbers);
// iterations: 25

Insertion sort
It's called insertionSort because we use splice to insert into the array when sorting.
Gist example Insertion sort

let nums = [10,5,3,8,2,6,4,7,9,1];
let insertionSort = nums => {  
let iterations = 0;
  // for each number starting on 2nd slot
  for (let i = 1; i < nums.length; i++) {
    //console.log("outer loop: " + nums[i]); // 5 (second number of array)
    for (let j = 0; j < i; j++) {
      //console.log("inner loop: " + nums[j]); // 10
      if (nums[i] < nums[j]) { // if 5 is less than 10
        // get one element from slot i (take from array, array gets modified)
        let spliced = nums.splice(i, 1);
        //insert spliced[0] in slot j, and displace array (if replace 0 for 1 slot 0 gets replaced instead of displaced)
        nums.splice(j, 0, spliced[0]);
        console.log("spliced: " + nums);
        console.log("number of iterations: "+ ++iterations)
      }
    }
  }
};
insertionSort(nums);
// number of iterations to sort: 9

The number of iterations got cut by half, neat!

Merge sort
Merge sort is the Algorithm most engines use when you run array.sort();
What merge sort does, is split array into 2 parts, then split those 2 arrays in 2, now we have 4 arrays, when the arrays can no longer be split in half, the algorithm starts to merge the numbers in order.

Merge sort algorithm is very stable because it does not move indexes if the numbers do get repeated.
Code example Merge sort

let nums = [10,5,3,8,2,6,4,7,9,1];
var iterations = 0;
const mergeSort = (nums) => {
    ++iterations;
    console.log(iterations);
    if(nums.length < 2) {
      return nums;
    }
    
    const length = nums.length;
    const middle = Math.floor(length / 2);
    const left = nums.slice(0, middle); //left part of the array
    const right = nums.slice(middle, length);
  
    const sortedLeft = mergeSort(left);
    const sortedRight = mergeSort(right);
    return stitch(sortedLeft, sortedRight);
}

const stitch = (left, right) => {
  const results = [];
  while(left.length && right.length) {
    if (left[0] <= right[0]) {
      results.push(left.shift());
    } else {
       results.push(right.shift());
    }
  }
  while(left.length) {
    results.push(left.shift());
  }
  while(right.length) {
    results.push(right.shift());
  }
  return results;
}

let result = mergeSort(nums);
console.log(result);

This representation of algorithms is for informational purposes; you should not use them in production, I recommend you use array.sort() native function for this purposes, since the code is written for humans and we should make our code understandable and semantic.

bibliography
http://www.visualcapitalist.com/intro-to-algorithms/

THOMAS H. CORMEN
CHARLES E. LEISERSON
RONALD L. RIVEST
CLIFFORD STEIN
Introduction to algorithms
2008
Massachusetts Institute of technology

  • LinkedIn
  • Tumblr
  • Reddit
  • Google+
  • Pinterest
  • Pocket