DEV Community: keeks5456

Sorting Algorithms: Merge Sort

keeks5456 — Wed, 07 Apr 2021 18:53:51 +0000

On today's series of Sorting Algorithms, I will be getting down with the Merge Sort Algorithm!

What Is A Merge Sort Algorithm?

Merge Sort is described as a divide and conquer algorithm. What this means is, we start off with an array of items, we must divide that array in half. Now that we have two arrays, we start comparing each element to the opposing array. Whichever is smallest, must go into the empty array. As a result, we return a new sorted array.

Now, before we get into the code, like the algorithm itself, we must break down how to implement merge sort in two functions!

Merge a Nearly Sorted array

In this function, we will be taking our array, splitting it down the middle, giving us two arrays. With recursion, we will keep splitting those two arrays until they are an array containing one element

The PseudoCode

Break up the array into halves until you have arrays that are empty or have be an element.
Once you have small & sorted arrays, merge those arrays with each other until they are back at full length.

The Code

//helper method to sort the array
const mergeSort = (arr) =>{
  //base case if our array length is too small.
  if(arr.lenght <= 1) return arr 

  //first split the array in half
  let mid = Math.floor(arr.length / 2)
  //assign the left half of the array from beginning to middle
  let left = mergeSort(arr.slice(0, mid))
  //assign the right half of the array from mid to end of array
  let right = mergeSort(arr.slice(mid))
  //return sorted array by calling merge function to merge the now sorted pieces together
  return mergeSort(left, right)
}

Merging Arrays

How we can approach this function is, with our two split up arrays from our mergeSort function, we will now start comparing if an element is the smallest in the left or right array, that element will get pushed into our results array.

The Pseudocode

Create an empty array, look at the smallest values in each array
while there are still values we haven't looked at,
if the value in the first array is smaller than the second array, push that value into the results and move to the next element in the first array.
This same logic goes for the second array, if the value there is smallest, push that to the results array.
Once we exhaust one array, push the remains from the other to the results array and return.

The Code


//create the merge function, it takes in two arrays 
const merge = (arr1, arr2) =>{
  //create a reults array to return merge srted array
  let results = []
  //assign i and j to 0 as comparison pointers 
  let i = 0, j = 0
  //create a while loop going through both arr1 & arr2 loping at each index
  // while there are still elements in our arrays, do this
  while(i < arr1.length && j < arr2.length){
    //ask if arr1[i] is less that arr2[j]
    if(arr1[i] < arr2[j]){
      //if arr1[i] is smaller, push that number in our results array
      results.push(arr1[i])
      //move to the next value in arr1
      i++
    } else {
      //if arr2[j] is smallest instead push that to our array
      results.push(arr2[j])
    }
  }
  //since there is a possibility of remaining elements in either of the arrays we must lop through them again while they are not empty
  //while there are still elements in arr1, iterate through them and push them to results array, these remaining elements will already be sorted because of merge helper function
  while(i < arr1.length){
    results.push(arr1[i])
    i++
  }
   //while there are still elements in arr2, iterate through them and push them to results array, these remaining elements will already be sorted becasue of merge helper funtion
  while(j < arr2.length){
    results.push(arr2)
    j++
  }
  return results
}

Without Comments

function mergeSort(arr1, arr2){
  let results = []

  let i = 0
  let j = 0

  while(i < arr1.length && j < arr2.length){
    if(arr2[j] > arr1[i]){
      results.push(arr1[i])
      i++
    } else {
      results.push(arr2[j])
      j++
    }
  }

  return results
}


function merge(arr){
  if(arr.length <= 1) return arr

  let middle = Math.floor(arr.lenght / 2)
  let left = mergeSort(arr.slice(0, middle))
  let right = mergeSort(arr.slice(middle))
  return merge(left, right)
}

Time and Space Complexity

The time complexity of a merge sort algorithm at best, average, and worst case is O(n log n).
The space complexity of this algorithm is O(n). ***

The Conclusion

The Merge Sort Algorithm is highly more effective than implementing Bubble Sort or Selection Sort. It simply breaks down the array only to build it back up again. Now that w are diving into the more advanced sorting algorithms, I will be talking about Quicksort and the advantages it has in sorting!

Until Next time!
Happy Coding :)

Sorting Algorithms: Insertion Sort

keeks5456 — Mon, 05 Apr 2021 17:03:57 +0000

In this next series of Sorting Algorithms, I will be talking about Insertion Sort!

What Is Insertion Sort?

Insertion Sort is a sorting algorithm that consumes an input element for each repetition and grows a sorted output. How this works is, at each iteration, the algorithm removes/ holds one element from the array, looks for the location it belongs to within the sorted list, and inserts that element back into the array at the correct sorted index.

Pseudocode

Start by picking the second element in the array.
Compare the second element with the element before i. Swap if that second element is greater than the one before i.
Continue to the next element, and if it is in the incorrect order, loop through the sorted portion, (the left side) to place that element in the current place.
Repeat till array is sorted.

The Code With Comments

function insertionSort(arr){
  //start looping at first index
  for(var i = 1; i < arr.length; i++){
    //assign a plae holder varible at the index of i to keep track f the value we are looking at
    var currentVal = arr[i]
    //start working backwards with variable j at the value behind i 
    // ex: if i = 9, we want to start comparing the value of i to the value of j --> j = 77
    //we need to keep going while j is greater than 0 (his up to the beginning of the array)
    //and while j is greater than currentVal variable 
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
          //ex: is currentVal = 9 smaller than arr[j] = 77 value, yes! then move arr[j] up in the array 
          //[2,4,5,20,77,77]            9 is waitning for its placement
      arr[j + 1] = arr[j]

    }
    //after the loop is done, we have found our placement for currentVal
    //we assign arr[j + 1] to currentVal b/c there will be a duplicate of arr[j] where it was before 
    //       j
    // [2,4,5,20,20,77]          9 waiting
    //       j+1 --> this is where 9 should be now
    arr[j + 1] = currentVal 
  }
  return arr
}
insertionSort([2,4,5,20,77,9])

The Code Without comments

function insertionSort(arr){
  for(var i = 1; i < arr.length; i++){
    var currentVal = arr[i]
    for(var j = i - 1; j >= 0 && arr[j] > currentVal; j--){
      arr[j + 1] = arr[j]
    }
    arr[j + 1] = currentVal

  }
  return arr
}

insertionSort([2,4,5,77,1,9])

The Explanation

Now, if sorting algorithms have got your mind all boggled up, don't worry, I was the same way when I first started learning.

Basically, we want to iterate over the array with our variable i at the first index. By first I mean the index of array[1]. We then assign that element into a variable called currentVal.

Now we need to start thinking about how we will be moving backward in our array. We do this by iterating through our array again with a variable j at the index behind i. During this loop, if the current value is smaller than arr[j], we need to move it hold on to that value you, go down the list of elements, and find the index it belongs to.

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

Our j variable does this by shifting the larger value elements up in the array.

 arr[j + 1] = arr[j]

Once we find that our currentVal variable is actually larger than an element at arr[j] we move up by one in the array and assign currentVal to that index

    arr[j + 1] = currentVal

Finally, out of the loop, we can return the sorted array.

Time & Space Complexity

The best-case scenario for a sorting algorithm like insertion sort is O(n).
We can obtain this during each iteration, the first remaining elements of the input is only compared with the right-most element of the sorted subsection f the array. This is achieved by using a while loop instead of a nested for loop.

Now, the worst-case senario for insertion sort is O(n^2), which is a quadratic running time. That is because, there is a nested for loop, which is looking through our array backward. Looking through and shifting the sorted subsection of the array before inserting the element into its right position.

The Conclusion

Now, even though Insertion sort is much more efficient & faster than Bubble sort and Selection sort when it comes to small array lengths. It can not handle a large list of arrays. However, there are more advanced sorting algorithms that I will diving into next time on this series of Sorting Algorithms! So Stay tuned for the next blog post :)

Happy Coding!

References

Learn more about Insertion sort

Sorting Algorithms: Selection Sort

keeks5456 — Fri, 02 Apr 2021 05:09:08 +0000

Today we will be discussing Selection Sort! What this algorithm does, is sort the items in place inside the array. Although, that may sound like it would be a fast way to sort an array, selection sort proves you wrong.

The Pseudocode

Write a function called selectionSort that takes an array as an argument.
iterate through the array with a variable i. Store the first element as the smallest value seen.
iterate through the array again with a variable of j at the next index of i.
if the our value at arr[j] has a smaller value than our lowest variable found, we can assign that value as the lowest.
if our value at the index of i is not the smallest value encountered. Start the swapping sequence.
Repeat the same steps with the next element until the array is sorted.

The Code

function selectionSort(arr){
  console.log(arr, 'original')
  for(var i = 0; i < arr.length; i ++){
    var lowest = i

    for(var j = i + 1; j < arr.length; j++){
      if(arr[j] < arr[lowest]){
        lowest = j
      }
    }
    // if our current i is not the lowest value, start switching
     if(i !== lowest){
      //create switch here
      var temp = arr[i]
      console.log(arr)
      arr[i] = arr[lowest]
       console.log(arr)
      arr[lowest] = temp
       console.log(arr)
       console.log(temp, 'temp holding at place for a switch')
       console.log(lowest, 'lowest @ index')
       console.log(arr[i], 'arr[i] has now became lowest')
        console.log(arr[lowest], 'arr[lowest]')
    }
  }
  return arr
  } 

selectionSort([7,9,4])

[ 7, 9, 4 ] 'original'
[ 7, 9, 4 ]
[ 4, 9, 4 ]
[ 4, 9, 7 ]
7 'temp holding at place for a switch'
2 'lowest @ index'
4 'arr[i] has now became lowest'
7 'arr[lowest]'
[ 4, 9, 7 ]
[ 4, 7, 7 ]
[ 4, 7, 9 ]
9 'temp holding at place for a switch'
2 'lowest @ index'
7 'arr[i] has now became lowest'
9 'arr[lowest]'
[ 4, 7, 9 ]

Explanation

The part to understand is how the swap works. Basically, if we find that i is not the lowest value, that's where the magic of swapping happens. If we find out that the value where i is place is not the smallest value, we must create variable temp and assign it in place of arr[i] as a place holder for swapping. We thin assign arr[i] with the value that arr[lowest] is holding. That will now place the smallest value in its correct position. The last swap in place is to assign arr[lowest] to temp, giving the lowest the large value in place close to where it needs to be.

The Time & Space Complexity

Given that our selection sort function has a nested for loop, along with a consistent amount of swapping with every comparison made to every other element in the array, this puts our Time Complexity at O(n^2). However, Space Complexity of this algorithm is O(1), we are swapping in-place of array, which means isn't a need for creating a new array or add extra space in our existing array.

The Conclusion

Well folks, that concludes my blog about Selection Sort! I hope this was helpful on your personal journey of how to understand Algorithms! Stay tuned for the next topic on Insertion Sort!

Happy Coding!

Sorting Algorithms: Bubble Sort

keeks5456 — Tue, 30 Mar 2021 00:21:13 +0000

Sorting Algorithms?

So, you're probably wondering, "What exactly are sorting algorithms?". Well, a sorting algorithm is simply used to rearrange a given array or some list of elements in an ascending or descending order. With the use of a comparison operator that decides the new order of the elements in the data structure.

An example would be if we had an array of unsorted numbers, we wanted our algorithm to sort them in ascending order.

[3,5,7,1,2] => [1,2,3,5,7]

Bubble Sort

Now, A Bubble Sort algorithm is one of the simplest sorting algorithms to understand. Bubble sort works by repeatedly swapping the adjacent elements if they are in the wrong order. Let's say we are ascending from smallest to largest in an array:

What Exactly Is Happening Here?

What our bubble sort algorithm is doing here is, through every single iteration, it is continuously comparing each pair of integers, determining where to place those two integers in regards to how we design the code. In the example above, it is sorting in ascending order from smallest to largest.

Pseudocode

Here are some steps to get you started on how you can implement a __bubble sort algorithm.

First, create a function called bubbleSort that takes in an array.
Using a for loop, with a variable i from the end of the array to the beginning.
Using an inner loop, with a variable of j that starts at the beginning and ends i - 1.
Compare if arr[j] is greater than arr[j + 1], swap those two values.
at the end return the sorted array

The Code

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

If you take a good look at this code, we aren't quite finished just yet! In the scenario of our data almost sorted or is already sorted, it doesn't need to be sorted again. Yet, right now our bubble sort algorithm doesn't regard if the array is somewhat or already there. If we had an array of lengths 32 or more, this kind of logic will take up unnecessary space.

To combat this, we can have checks within our code asking, "Did we make any swaps here?", If no, then we must be done in our iteration.

Opimization

So, to optimize this code to prevent unnecessary swapping from happening, we can use a noSwaps variable that will take in a boolean.

function bubbleSort(arr){
  var noSwaps;
  for(let i = arr.length - 1; i > 0; i++){
    noSwaps = true
    for(let j = i -1; j < arr.length; 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
        nSoSwaps = false
      }
    }
    if(noSwaps) break
  }
  return arr
}

Here, if there aren't anymore swaps within an iteration, we must break out of the code and return our array. This gets rid of the unnecessary actions of our code iterating through the area for a possible swap.

Conclusion

That concludes this blog on bubble sort! Stay tuned for my next blog that will focus on Selection Sort

LeetCode: pathSum

keeks5456 — Mon, 01 Mar 2021 04:25:57 +0000

The Problem

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

What this means is, we are traversing through a tree from root down to a leaf path indicated in blue on the example image below:

The information we know is our input and output here:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

We want to return true if there is a path in our tree that is equivalent to our targetSum. If we do not find that path, we must return false.

The Approach

There are a few ways we can approach this problem, one way is by solving it using good-old recursion.

We first start off by establishing an edge case, we make sure that if the root is null, meaning if there aren't any nodes attached to our root, we must return false.

We then need to add a case where, if our targetSum is found and there are no more children on the left and/or right of the last node, we can return true! Now, what I mean by that is, let's say we have this tree to traverse through:

As you can see, from the root that is 7, when we traverse to the left of that tree, we can see that it adds up to 14. 3 is our last node child so we can return true. However, if 3 had other children to traverse through, this would be considered a false path because we need to traverse through the whole path and add that up to 14!

Lastly, what we want to do next is recursively call our left or right children if we are not at the last node child in the tree. Basically, keep moving down the path until we are at the final node.

The Code

var hasPathSum = function(root, targetSum) {
    if(root === null) {
        return false 
    }

    if(root.left == null && root.right == null && targetSum == root.val) return true

    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
};

Refrences

Here is a youtube video that better explains how to approach this algorithm!

pathSum

Thank you for taking the time to read this blog! Please leave any comments, other ways to approach this code challenge, or any advice for other junior developers to benefit from :)
-- Happy Coding <3