DEV Community: mosemet

Sorting Algorithms in 3 Minutes

mosemet — Tue, 14 Sep 2021 22:30:19 +0000

Bubble Sort Algorithm

Bubble sort is a simple sorting algorithm that repeatedly steps through the array, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.

function swapSort (array) {
    let i, j
    for (i = 0; i < array.length - 1; i++){
        for (j = i + 1; j < array.length; j++){
            if (array[i] > array[j]){
                [array[i], array[j]] = [array[j], array[i]]
            }
        }
    }
    return array
}

Min Sort Algorithm - Custom

Min Sort or Minimum sorting algorithm is a custom algorithm I created when I started studying sorting algorithms. It merely grabs the minimum element within the array, pushes the minimum element into a new array, and also deletes that minimum element from the old array. So it will get a new minimum with each iteration until the new array is sorted. I found it quite handy as it was straightfoward to implement using built-in functions.

function minSort (array) {
    let i, j, result = [], len = array.length
    for (i = 0; i < len; i++){
        for (j = 0; j < len - i; j++){
            if (array[j] === Math.min(...array)){
                result.push(array[j])
                array.splice(j,1)
            }
        }
    }
    return result
}

Selection Sort Algorithm

Selection sort algorithm divides the input list into two parts: a sorted sub-list of items which is built up from left to right at the front (left) of the list and a sub-list of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sub-list is empty and the unsorted sub-list is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sub-list, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sub-list boundaries one element to the right.

function selectionSort(array) {
    let i, j
    for (i = 0; i < array.length - 1 ; i++){
        let min = i  
      for (j = i + 1; j < array.length; j++){
        if (array[j] < array[min]){
          min = j
        }
      }
      if (min !== i){
        [array[i], array[min]] = [array[min], array[i]] 
      }
    }
    return array
  }

Quick Sort Algorithm

Quicksort is an in-place sorting algorithm. It is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.[4] The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Animation:
An animation on how the algorithm works can be found here.

function swap(arr, x, y) {
  [arr[x], arr[y]] = [arr[y], arr[x]];
}
function pivot(arr, left = 0, right = arr.length - 1) {
  let shift = left
  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < arr[left]) swap(arr, i, ++shift);
  }
  swap(arr, left, shift);
  return shift;
}

function quickSort(array, left = 0, right = array.length - 1) {
  if (left < right) {
    let pivotIndex = pivot(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
  }
  return array
}

Merge Sort Algorithm

In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.

Conceptually, a merge sort works as follows:

Divide the unsorted list into n sub-lists, each containing one element (a list of one element is considered sorted).
Repeatedly merge sub-lists to produce new sorted sub-lists until there is only one sub-list remaining. This will be the sorted list.

function merger(arr1, arr2) {
    let i = 0, j = 0, mergedArr = [];
    while (i < arr1.length && j < arr2.length) {
      if (arr1[i] > arr2[j]) mergedArr.push(arr2[j++]);
      else mergedArr.push(arr1[i++]);
    }
    while (i < arr1.length) {
      mergedArr.push(arr1[i++]);
    }
    while (j < arr2.length) {
      mergedArr.push(arr2[j++]);
    }
    return mergedArr;
  }
  function mergeSort(array) {
      if (array.length === 1) return array;
    let middle = Math.floor(array.length / 2);
    let left = mergeSort(array.slice(0, middle));
    let right = mergeSort(array.slice(middle));

    return merger(left, right);
  }

Effective use of Array.prototype Methods.

mosemet — Tue, 07 Sep 2021 16:06:33 +0000

Array methods are some of the most usefull concepts to master but also quite tricky in what each returns, what it takes as parameters and exactly what does it do to the array.

First defining a prototype. A prototype is a global constructor available for all JavaScript objects and allows the user to add new properties and methods to the array. We can create a new method that provides the sum for an array as follows:

Array.prototype.myArraySum = function () {
     let sum = 0
     for (let i = 0; i < this.length; i++){
         sum += this[i]
        }
         return sum
    }
const array = [1,2,3,5]
console.log(array.myArraySum()) //11

From the example above, we can deduce what a prototype is. It models something, and tells it how to look or behave. A method, is therefore simply a function that is defined on an object. In the example above, the object would be array and the method is myArraySum. It should be noted that myArraySum doesn't take any argument. However most inbuilt JavaScript Array methods take callbacks and other parameters.

A callback function is a function that is applied in another function as an argument, which is then invoked inside the outer function. Let us try to use a callback inside a prototype method:

Array.prototype.someMethod = function (callback) 
    {
       //Do something
       //Return the result
    }
const array = [1,2,3,4]
console.log(array.someMethod(function (a) => { 
  return a*2))

From the example of myArrySum above, we can apply a callback to understand a better on the inner mechanism of prototype methods.

Array.prototype.myArraySum =  function (callback) {
  let bound = callback.bind(this);
    bound();
     let sum = 0
     for (let i = 0; i < this.length; i++){
         sum += this[i]
        }

         return bound(sum)
    }
const array = [1,2,3,5]
console.log(array.myAarraySum((a) => a**2 - 2*a + 7)) //106

Applying a callback to myArraySum gives it more power. The callback does not change what the function does, which is giving a sum of an array, but it can definitely give us flexibility to do something to the sum without extra lines of code. In this case, we have applied a polynomial to indicate the power of callbacks. myArraySum will always return a number, NOT another array. We need to understand what the method returns. That, in my book, is most important when choosing what method to use.

JavaScript has inbuilt Array.prototype methods, which can be accessed on this link.

A deeper dive of these array methods will be explored in these series.

1 Line Caesar Cipher

mosemet — Sat, 21 Aug 2021 19:36:06 +0000

In cryptography, a Caesar cipher, also known as Caesar's cipher, the shift cipher, Caesar's code or Caesar shift, is one of the simplest and most widely known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet. For example, with a left shift of 3, D would be replaced by A, E would become B, and so on. The method is named after Julius Caesar, who used it in his private correspondence.[1]

The encryption step performed by a Caesar cipher is often incorporated as part of more complex schemes, such as the Vigenère cipher, and still has modern application in the ROT13 system. As with all single-alphabet substitution ciphers, the Caesar cipher is easily broken and in modern practice offers essentially no communications security.

For example, shifting each of the 26 letters of the English alphabet by 3 places to the left, is equivalent to shifting by 23 places to the right. A plain text message without encryption applied is below:

Plaintext:  THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG

To take a look at what is going on, we can take the letter A. shifting A to the left by 3 places, with 1 shift, we get Z, with 2 shifts, we get Y and with 3rd shift we get X. With this cipher, this is done for all letters of the alphabet and shifted.

Ciphertext: QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

To decrypt, one will need to shift each letter of the encrypted in the opposite direction to which it was shifted. So A is now X, to get back to A, we shift to the right by 3 to get back to A.

In order to do this computationally, this encryption uses modular arithmetic by transforming the letters to numbers. Computers use ASCII code. From ASCII tables, A is 65, counting incrementally until Z is 90, and a is 97, counting incrementally to z which is 122.

The complete code is given below:

const caesarCipher = (str, shift=13) => str.replace(
  /[A-Za-z]/g, char => String.fromCharCode(
    65 + ((char = char.charCodeAt()) & 32) +((char&~32) - 65 + shift) % 26
  )
)

The char.charCodeAt() merely transforms the given character, char to its ASCII number, while the String.fromCharCode() method transforms the given number back to its alphabetic form. Now using this inside the Array.prototype.replace() method, we are simply replacing a given English alphabet with a shifted ASCII alphabet, thus scrambling the message.

It is worth noting that Caesar cipher is one of the most famous encryption algorithms in simplicity and cannot offer any information security.

Do you Understand this... ?

mosemet — Sat, 21 Aug 2021 19:20:49 +0000

What is this and what context is it used?

To understand this segment, we will have to head to an IDE. For simplicity, I will be using the Eloquent JavaScript IDE on this link.

When the command console.log(this) gives access to the Window object. The Window object represents an open window in the browser. The browser creates a window object for the HTML document and also all the tags that make up the HTML document. Click this link to have a look at Window Object Properties and Window Object Methods. console.log(typeof this) returns Object. Below is the snippet of the actual window object logged.

They look very similar to W3Schools.com website link window objects properties and their methods.
console.log(this.origin) returns https://eloquentjavascript.net😎. Inside the window object, name leads to an empty string, hence console.log(this.name) returns nothing since it's an empty string. A made up name on the other hand: console.log(this.anyName) returns undefined since there has not been any declaration to anyName and it does not exist in the window object. However, let anyName = 'myName'; console.log(this.anyName) returns myName🤓.

Context

When this is used inside a function, it refers to an object in which it is bound. It simply refers the function to where it should get its data from.

Calling this function: let whyMe = 'It is getting clearer'; whatIsThis() prints It is getting clearer. However, we still have access to the window objects when needed even inside a function. It is worth noting that whyMe() is now bound to the global scope and this.whyMe references that global scope.

In the above code, name, action, toy and Function are all properties of myObject. Accessing this properties we can use the .dot method. Hence accessing the function Function from myObject runs testing, which then receives global scope from the window and appends to the respective properties.

Hope this clears something the confusion for beginners.

Think recursively...

mosemet — Fri, 13 Aug 2021 13:36:47 +0000

What is Recursion:

- An act of a function calling itself.

For example, below is the pseudo-code to show how recursion works. The function called recursion is being executed twice, first in the global scope, then secondly, within itself. The function can then be called however the user chooses.

According to the Church-Turing hypothesis, any function that can be computed iteratively, can be computed recursively and vice versa (loosely translated). This function can take two cases.

A base case - to end the recursion
An iterative case - continues the recursion

A recursive function will call itself until the base case breaks the call. In this case the base for the below recursive function is

if (num <= 0)

This function will return 0 as the answer. It will continue to call itself recursively, decrementing by 1 (num -1) for every call. For each call num will take values of 5, 4, 3, 2, 1 until the base case of num = 0 hits, which will then trigger the return 0.

Taking a simple function that adds elements of an array: let array = [3,2,3,6,5]. The problem can be solved quite easily with a for loop. Looping through the elements of the array and adding to each element. However, we also know from the Church-Turing hypothesis, that we can also execute the same recursively.

A for-loop sum function below:

The recursive sum function is below:

The recursive sum function is shorter, than using the for-loop. This is usually the case even for more complex functions. The base case for the recursive function is if (arr.length > 0). This function will call itself as long as the length of the array is not 0. Once this length becomes 0, it executes the return.

To understand exactly what is happening, we will need to employ the services of our old friend,
console.log() with a more robust example of arithmetic mean. This is what is commonly referred to an an average.

This function increases the count as the function calls itself repeatedly. This is quite useful in many ways. One, we can know how many times the recursion occurred. However, since The size of the array also reduces with each call, arr.length also changes. This means if we try to simply return init / arr.length, we will be dividing by 0 as arr.length reduces to 0. Why is that? You guessed, it, the use of the arr.slice(1). The slice method, in this case, removes the first element from the array and returns a new reduced array on every recursive call.

Hence increasing the count is handy as the count can be used in place of arr.length as it increments to the size of the original array. The init argument is where the magic happens. Since the initial value of init = 0 at the start, it is updated through arr[0] + init. This means a new value of init will have the first element of the array added to it on every call, ensuring that when the base case has been met, all the init contains the sum of all the elements of the array. Now, when we return init, we are simply returning the sum of the elements of the array. Also, because count + 1 ensures the count increases from the declaration value count = 0, it increases by 1 on every recursive call, ultimately matching the length of the array, hence we can simply do return init / count will give us the sum of the elements divided by the number of elements within the array, which is the arithmetic mean.

Note the formulae of arithmetic mean, geometric mean and harmonic mean is below for referrence.

I try to challenge myself to change functions written using for loop to recursion. This is so I can challenge myself to understand what happens each time a function is called. Notice that everything within the recursive function will update on each call. The same logic can be followed for geometric and harmonic mean. Doing trivial exercises helps one understand the mechanics of the code, for loops are easy to follow, recursion isn't as clear-cut as loops, but setting a count so you know how many times the function was called helps mentally map what is happening.

I hope this helps you as much as it helped me. Below are the codes for both geometric and harmonic mean. Note that init = 1 and not init = 0. Happy recursions.