Forem: MCFrank16

Understanding Merge Sort in Javascript.

MCFrank16 — Wed, 24 Jun 2020 08:55:16 +0000

Sorting Algorithm Articles
Bubble Sort
Selection Sort
Insertion Sort

Welcome to the second part of the sorting algorithm, from this article, we are going to face some intermediate sorting algorithm starting with Merge Sort.

These algorithms are way faster than the ones we saw already Bubble, Selection, and Insertion sort and the reason behind is that they do scale well; i.e: they do work pretty well on a large amount of data.

if for example, we compare Merge sort and bubble sort worst-case scenarios, merge sort's time efficiency would be O(n log n) which is better than the quadratic complexity O(n^2) of bubble sort.

As others, Merge sort is also a comparison based algorithm, and it exploits the facts that arrays of 1 element are always sorted, it employs a divide and conquer algorithm pattern, where it has to first divide an array till it reaches the point where only an array of 1 or empty element is left. after that process, it then starts to merge those single elements together by comparing one array's elements to the other.

Let's quickly look into merge sort pseudo code

we will first break the given array into halves until we have an array that has one element or which is completely empty.
once we have smaller sorted array, merge those arrays back together until you're back to the full length of the array.
And once the array has been merged together, return the merged array.

As the pseudo-code says, we need to merge back the sorted array, so for that, we will need to implement a helper function that will do that job for us.

Merging Array (Helper function)

this function should run in O(n+m) in time efficiency because we are iterating on each item in the array once.

function merge(arr1, arr2){
  let result = []; // the array to hold results.
  let i = 0; 
  let j = 0;

// as the pseudo-code implies, we have to loop through the 
// arrays at the same time and it has to be done once.
// note that if one array completes its iteration, we will
// have to stop the while loop.

  while(i < arr1.length && j < arr2.length){
// compare the elements one at a time.
    if(arr1[i] > arr2[j]) {
      result.push(arr2[j]);
      j++;
    } else {
      result.push(arr1[i]);
      i++;
    }
  }

  // these other while loops checks if there's some item left
 // in the arrays so that we can push their elements in the result array.
  while(i < arr1.length){
    result.push(arr1[i]);
    i++;
  }

  while(j < arr2.length){
    result.push(arr2[j]);
    j++;
  }

  return result;
}

Below is the merge sort function implemented
it splits the array into two halves and then splits those arrays till it reaches a single array element. Remember that principle.
it merges the arrays using the helper function we created above.

function mergeSort(arr){

// recursion base case
// it checks if the array length is less than or equal to 1.
// if that's the case return the arr else keep splicing.

  if(arr.length <= 1) return arr;
  // remember that we said merge sort uses divide and conquer
// algorithm pattern

// it firsts know the half point of the array.
  let halfPoint = Math.ceil(arr.length / 2);

// and then splice the array from the beginning up to the half point.
// but for the fact that merge sort needs the array to be of one element, it will keep splicing that half till it fulfills the condition of having one element array.

  let firstHalf = mergeSort(arr.splice(0, halfPoint));

// second array from the half point up to the end of the array.
  let secondHalf = mergeSort(arr.splice(-halfPoint));

// merge the array back and return the result.
// note that we are using the helper function we created above.
  return merge(firstHalf, secondHalf);
}

That is all about merge sort implementation but as always we have to wrap it up after looking at Big O Notation analysis.

To understand it better, let's decompose the steps the algorithm will take in order to sort the array.

Based on the length of the array, the algorithm needs to first decompose the array until it reaches a single-element array.

so the analysis question will be how many time will I have to split this array this it reaches to a single-element array. and that is O(log n).

Also Remember we have to merge back the array and compare their elements so that they can be sorted, and here the loop will grow proportionally to the length of the array. so the process of merging back the arrays will be linear O(n + m) which we simplify back to O(n).

And then if we add both O(n) + O(log n) = O(n log n) in every case scenarios

Worst-Case Scenarios: O(n log n)
Best-Case Scenarios: O(n log n)
Average-Case Scenarios: O(n log n)
Space complexity: O(n), and this is due to the fact that it has to store multiple chunked arrays in the memory.

Yeah, That is all I got on Merge Sort and I hope you enjoyed it. for any question you can slide in my DM here or on Twitter

Ciao.

Understanding Insertion Sort in Javascript.

MCFrank16 — Mon, 15 Jun 2020 07:42:27 +0000

This is a continuation of the sorting algorithm techniques in javascript. You can find links to previous articles below:

Sorting Algorithm Articles
Bubble Sort
Selection Sort

A quick definition of insertion sort is that it builds up the sort by gradually creating a larger left fraction of the array which is always sorted.

Let's say we have [5,3,2,6,8] as our initial array, insertion sort will assume 5 is already sorted, and then selects the next element which is 3 and compare it to 5, and if 3 is less than 5, then that means 3 should be inserted right before 5, but when the next element is greater than 5, then that element will remain in its position. So that's how the sorted array gradually grows little by little.

Let's take a look at insertion sort pseudo code.

we start by picking the second element of the array.
we compare it to the element before it, and swap if that element is less than the one before it.
then continue to the next element, and iterate through the left portion, which is sorted by the way and try to insert that current element in its correct place in the sorted portion.
repeat this process until the array is sorted, and make sure you return the sorted array.

Alright, It's time to get our hands dirty now.

const insertionSort = (arr) => {

  // as the pseudocode implies, we need to start looping from
  // the second element by assuming the first element is in
 // left portion of the array which is always sorted.

  for(let i = 1; i < arr.length; i++){

    // we also need to select our actual current element,
   // this will aid us to compare it to the values of our
  // sorted portion and also finding its correct spot.

    let currentEl = arr[i];

  // the next loop will help us go through the sorted portion
  // of the array, and notice that it always goes behind i.
  // and it keeps going as long as it is still greater or equal to 0,
  // with that said, it loops until it hits the end of the
  // portion of the array, which is the beginning of the actual
  // array in this context.

  // Eg: imagine a scenario where i = 10, then j will be 9,
  // and j has also to walk backwards, which will help it to
  // compare the currentEl to the values in the sorted portion.
 // so that is the reason why it decrements instead of incrementing.

  // but when the currentEl of i is less than the one of j, that
 // when it is like this 536 >  89. then that mean we have found 
 // a new value to insert in our sorted portion.
 // that is what that condition arr[j] > currentEl means in that
// loop. note that the condition can also be written inside the
// inner loop scope.

    for(var j = i - 1; j >= 0 && arr[j] > currentEl; j--){

       // so here is where the exchange of numbers begins,
       // when it has been found that the arr[j] > currentEl,
       // then in the sorted array, we exchange the current value of
       // arr[j + 1] to be the value of arr[j] and decrement j.      
       // we will repeat this process till arr[j] < currentEl or 
       // when the loop end; 

       arr[j+1] = arr[j]; 
    }

    // from the operation above, j has moved down because it is no longer greater than the currentEl, and that is the magic moment for us.
   // cause now we know where our currentEl from i belongs, 
  // and that is just in front of the current j, which is j + 1. note also that we are doing this operation in the outer loop scope, 
  // and j is available because we made it global while initiating it.

    arr[j+1] = currentEl;
  }

  // and finally, we return our sorted array.
  return arr;
}

insertionSort([345,56,96,2,39,70.-0.65,-0,13,65,-54,134,536,89,223,6890,5,12134]);

let's walk through it again in a different way to concretely understand it.

  // suppose we have this array below, and it needs to be sorted.
   arr = [546,2,876,-1,6];
   // firststep, i = 1, currentEl = arr[i] which is equal to 2.
   // j = 0, and we compare arr[j] > currentEL. i.e: is 546 greater
  // than 2, and that is true.
  // we move 546 ahead by replacing a value which was on arr[j + 1] with the value of arr[j].
// and now our array looks like this inside the inner loop
arr = [546,546,876,-1,-6]
// and remember we have saved our currentEl which is 2.
// after that j decrements to -1, and that means its loop finishes
// because j is no longer greater or equal to 0. it is now -1 which
// is less than 0.
// in the loop scope of i. i.e: the outer loop, we need to exchange our numbers.
// and our array is like this.
        0   1   2   3  4
arr = [546,546,876,-1,-6]
// j is now -1 and the correct spot of our currentEl which is 2,
// is on 0 index, so that is why we say that arr[j + 1]. i.e: arr[-1 + 1]
// which results in arr[0] should equal to our currentEl value.
// so now our array looks like this
arr = [2, 546, 876, -1, -6]
// after this operation, as we are in the outer loop, i will be // incremented to 2, so now let's look at the second step.

// our current arr looks like this 
arr = [2, 546, 876, -1, -6]
// second step: i = 2, currentEl = 876.
// j = 1. arr[j] = 546.
// compare is 546 > 876? the answer is no.
// decrement j to 0, and check if 2 > 876. the answer is NOO.
// decrement j to -1, and boom we're out of j loop.
// our current arr is still like this
arr = [2, 546, 876, -1, -6] // as there's nothing to sort at the moment
// loop of i again, and let's now increment i to 1.
// now i = 3, currentEl = -1.
// j = 3 - 1 (2), arr[2] = 876.
// is 876 > -1, YES, and exchange values.
arr = [2, 546, 876, 876, -6]
// decrement j to 1 and check if 546 > -1, and that is true.
arr = [2, 546, 546, 876, -6]
// decrement j to 0, and check if 2 > -1, TRUE. 
arr = [2, 2, 546, 876, -6]
// decrement j to -1, and we are out of its loop scope now.
// perform the operation arr[j+1] = currentEl.
// which means arr[-1+1] = -1, j = 0, currentEl is -1.
arr = [-1,2,546,876,-6]
// after that we increment i to 1, and its value is now 4
// currentEl is arr[4]. the value is -6.
// j = 4 - 1, arr[j] = 876.
// check if 876 > -6. TRUE, moves 876 to j + 1
arr = [-1,2,546,876,876]
// decrement j to 2 and check if 546 > -6. TRUE
arr = [-1,2,546,546,876]
// decrement j to 1 and check if 2 > -6. TRUE
arr = [-1,2,2,546,876]
// decrement j to 0 and check if -1 > -6. TRUE
arr = [-1,-1,2,546,876]
// decrement j to -1 and we're out of its loop.
// perform the operation of exchanging arr[j+1] = currentEL
arr = [-6,-1,2,546,876] // and we increment i to 5 and i is no longer 
// less than the length of the array which 5. is 5 < 5. NO
// this will get us out of the outer loop of i. and then
// we return our current array which looks like follow
arr = [-6,-1,2,546,876] // and BOOM, we are sorted now.

last but not least, let's talk a little bit about the BIG O NOTATION of insertion sort.

worstcase scenarios: it is quadratic O(n^2)
averagecase scenarios: it is also quadratic.
bestcase scenarios: it is linear O(n).

below is a quick picture of the BIG O notation of all the sorting algorithm we looked at so far.

And that's it. and thanks for reading this far.
Keep Learning, Keep Growing.
hasta la proxima vez

Understanding Selection Sort in Javascript.

MCFrank16 — Wed, 10 Jun 2020 05:30:01 +0000

This is a continuation of the sorting algorithm techniques in javascript. You can find links to previous articles below:

Sorting Algorithm Articles
Bubble Sort

Alright, let's get in straight to selection sort.

The prerequisites to better understand this sorting algorithm, you are required to have a better understanding of BIG O NOTATION and Bubble sort, so if it's your first time to hear them. I got you covered, just follow the link above in the table.

What is selection sort and how does it work?

Selection sort as the name implies is also a comparison sorting algorithm, where it has to walk or loop through a given datastructure and compare each number for the sake of computing a minimum number, so that in the end it can swap it with the number found at the beginning of the array.

Selection Sort is similar to bubble sort, the only slight difference is that instead of placing the sorted items in the end of the array as bubble sort does. It places them in the beginning, And the value placed in the beginning is always the smallest among others.

Let's first review the Selection Sort Pseudo Code

store the first element index as the smallest value, you've seen so far.
walk through the array and try to find another smallest value compared to the initial one.
if the smaller number is found, designate that number index to be the new minimum. note that we are working with indices here which basically helps us in swapping numbers.
if the current minimum is not equal to what we initially began with, swap the 2 values.
And repeat this process with the next element until the whole array is sorted. the reason why we select the next element is to avoid the redudancy of going through the already sorted elements.

// a swap helper function.
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]];

const selectionSort = (arr) => {
  // start looping at the beginning of the array.
  for(let i = 0; i < arr.length; i++) {
    // select the element's index at the beginning as the current minimum number.
    let min = i;
    // loop thourgh the array from the next element of the array
   // this will help us in checking only against the unsorted
   // elements, as we know the elements before it are already sorted.
    for(let j = i + 1; j < arr.length; j++){
      // check if the current element is less than the initial minimum
     // and assign the minimum to be the current element if that's the case.
      if(arr[j] < arr[min]) min = j;
    }
    // at this stage, we are checking if the new minimum index number
   // is not equal to the one we begin with.
   // analyse the code, and you will notice that we are still in the outer loop where i is still 0.
   // which was our initial minimum number value, so after
   // looping through the array again with the inner loop and 
  // we found another new minimun number, we are now swapping those 2 values.
 // after that, we repeat the same process until the array is sorted.
    i !== min && swap(arr, i, min);
  }
  return arr;
};

so that's the implementation of selection sort but we also need to look into its BIG O NOTATION.

for the worst case scenarios, let's say we have an array with 1M elements, the selection sort will have to loop 2M times for it to sort the array and that is not efficient at all. so it is Quadratic O(n^2)

the same analogy applies even on best and average case where it is O(n^2), just because of its behaviours of looping everytime from the beginning with any optimazition.

its time complexity makes it the worse one compared to others because it takes forever to sort even a nearly sorted array.

based on the fact, that we are only initiating 3 variables (min, i, j). This makes its space complexity constant O(1), there are no other variables required other than that.

And Yeah, That's it folks, until next time when we'll be looking at Insertion Sort.

Dios te bendiga.

Understanding Bubble Sort Algorithm in Javascript.

MCFrank16 — Mon, 08 Jun 2020 06:06:48 +0000

Welcome to the very first article of the sorting algorithm series, where we will be looking at different sorting algorithms.

Prerequisites: BIG O NOTATION.
if this is your first time to come across the term "BIG O NOTATION",I recommend you to head over to this article BIG O NOTATION and get accustomed to it first as it is important to learn how the algorithm performs in terms of time and space complexity.

Alright, let's now begin.

A quick definition of bubble sort is that, it bubbles up at the top the largest element inside an array. by bubbling up, I mean that It moves that value or an element inside the array at the end.

let'say we have an array with [1,3,8,5,7], after the first loop the array will end up like this [1,3,5,7,8] and as you can see the largest element which is 8 in this context has been bubbled up at the top.

By that we know that the largest element has been found and placed in a safe place where we don't need to touch it again, and then bubble sort repeats this process until all the largest element are placed at the end of the array.

I know this will be clear once we start to implement it, so here is the pseudo code:

Start looping from the end of the array with a variable called i that goes down until the beginning.
initiate an inner loop inside the outer loop with a variable called j, it loops from the beginning of the array until i - 1.
compare and check if arr[j] is greater than the next element which is arr[j+1]. if that's the case Swap those value. Swapping will allow us to move the largest element till it reaches the top of the array.
Finally after all this process, we will simply have to return the array,And put in mind that we will use the same array passed in as an argument without initiating a new one.

const bubbleSort = (arr) => {
  // this is a function which will help us in swapping 2 elements
  const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]];

  // start looping from the end of the array
  // this will help us in keeping track of the already sorted item so that we don't check it again.
  for(let i = arr.length; i > 0; i--){
    // start looping from the beginning of the array until i - 1.
    // this loop starts from the beginning and stops right in front of the current i.
    // as I said up earlier, there is no need to check against some already sorted items.
    for(let j = 0; j < i - 1; j++){
      // compare the current element to the next one, and swap
      // it swappes only if the current element is greater than the next element.
      if(arr[j] > arr[j+1]) swap(arr, j, j + 1);
    }
  }
  // return our sorted arr.
  return arr;
}

The very basic thing to pay attention to in this implementation and all other comparison sorting algorithm is the looping process, once you understand it you can implement it by your own.

We can also optimize it by keeping track of swaps process for the sake of time complexity and only swap when the if condition is valid, we can achieve that by initializing a noSwap variable. let's take a look at its implementation below

function bubbleSort(arr){
  let noSwaps; // noSwaps variable initialization.
  for(let i = arr.length; i > 0; i--){
    noSwaps = true; // setting it to true at first, by assuming there is no swaps for every time we loop through the values.
    for(let j = 0; j < i - 1; j++){
      if(arr[j] > arr[j+1]){
        let temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
        noSwaps=false; // if we make a swap, set it to false so that we keep comparing the elements.
      }
    }
    // if we don't make any swaps just break out of the loop.
    if(noSwaps) break;
  }
  return arr;
}

Before we wrap up, we also need to talk about BIG O NOTATION of bubble sort.

in general for worst case scenarios which is what we should care on because it is hard to know the state of your data structure, its time complexity is quadratic O(n^2).

for the average case scenarios, its time complexity is also quadratic O(n^2).

for the best case scenarios which applies to the nearly sorted array, the time complexity is linear O(n).

the space complexity of bubble sort is constant O(1), as we don't define many variable to consume the memory.

And that's everything about bubble sort fellow developers, and next time we will look into selection sort which is basically the opposite of bubble sort.

so keep your eye open for that next article and feel free to ask me any question on twitter as Me on Twitter

Dios te bendiga.