DEV Community: Toni Domazet

Quicksort sorting algorithm

Toni Domazet — Mon, 10 Dec 2018 15:00:09 +0000

Quicksort is a sorting algorithm. It's a divide-and-conquer algorithm that sorts a sequence by recursively dividing it into smaller subsequences. Let's see our function:

function quick_sort(array) {
    if(array.length < 2) return array;

    const pivot = array[0];

    let lower = array.filter(e => e < pivot),    
        greater = array.filter(e => e > pivot);

    return [...quick_sort(lower), pivot, ...quick_sort(greather)];
}

quick_sort([7,5,9,4,8,2])

Empty arrays and arrays with just one element are the base case. Nothing to sort here, and we can just return those arrays as is.

Quicksort algorithm starts with picking a pivot. There are many ways to choose a pivot:
• 1st element (as we do)
• last element
• median of the array as a pivot
• a random element as the pivot

const pivot = array[0];

After filtering collection (array) we have:
• A sub-array of all the numbers lower than the pivot
• The pivot
• A sub-array of all the numbers greater than the pivot

return [...quick_sort(lower), pivot, ...quick_sort(greater)];

Call quicksort recursively on the two sub-arrays (lower and greater) to break down the collection into single-element lists (hitting the base case), before combing them into one sorted list.

Here are all the steps (stack) depending on pivot we pick.

The Basics of Array.from()

Toni Domazet — Thu, 04 Oct 2018 12:08:51 +0000

Array.from() method allows you to create a shallow copy of:

Array-like objects (objects with a length property and indexed elements)
iterable objects (such as Map and Set)

In order to be iterable, an object must implement the @@iterator method, meaning that the object (or one of the objects up to its prototype chain) must have a property with a @@iterator key which is available via constant Symbol.iterator:

a = new Map([[ 1, 5 ]])
isIterable = typeof a[Symbol.iterator] === 'function'; //true


b = { 1: 5 }
isIterable = typeof b[Symbol.iterator] === 'function'; //false

Shallow Copy

A shallow copy will duplicate the top-level properties. If any of the properties are the objects, their reference addresses are copied.

Making changes to one array doesn't infect another array. Removing the last element from an original array will not change the length of the copied array, as it will remain the same.

let arrayOne = [ 1, 2, 3 ]
let arrayTwo = Array.from(arrayOne)

arrayTwo.pop()

console.log(arrayOne) //[ 1, 2, 3]
console.log(arrayTwo) //[ 1, 2 ]

The exception is the objects which are shared between the original and the copied array as they're pointing to the same reference stored somewhere in memory.

let arrayOne = [ 1, 2, [3] ];
let arrayTwo = Array.from(arrayOne)

arrayOne[2][0] = "abc";

console.log(arrayOne) //[ 1, 2, ["abc"] ];
console.log(arrayTwo) //[ 1, 2, ["abc"] ]

Map function and Array.from

Array.from() has an optional parameter mapFn, which allows you to execute a function on each element of the array.

Use Array.from() to create an array of the desired length, and calling a map function for every element of array to collect their squared values into a new array:

Array.from({ length: 5 }, (v, i) =>  i * i); //[0, 1, 4, 9, 16]

Three ways to check for palindromes in JavaScript

Toni Domazet — Tue, 11 Sep 2018 15:54:31 +0000

A palindrome is a word or a phrase that is the same whether you read it backward or forwards, for example, the word 'level'.

I'm going to create three different functions that are doing the same job - palindrome check for a passed string. I will mesure time of function execution to see which one of this function gives the best performance using performance.now() Web API method.

Create an array

isPalindrome = (string) => {
  string = string.toLocaleLowerCase();
  return Array.from(string).toString() === Array.from(string).reverse().toString()
}

//0.52 ms

Array object has a lot of useful methods - one of them is reverse(), but first, we need to create an Array from a string. After reverse, the first array element becomes the last, and the last array element becomes the first. We can't do check now, because condition will always be false as they're objects with different locations in memory. toString() method will return a string from our arrays.

Recursion

isPalindrome = (string) => {
  let strLen = string.length;
  string = string.toLocaleLowerCase();

  if (strLen === 0 || strLen === 1) {
    return true;
  }
  if (string[0] === string[strLen - 1]) {
    return isPalindrome(string.slice(1, strLen - 1) );
  }  
  return false;
};

//0.30 ms

Recursion is a process when a function calls itself to solve a problem. In our code, function is called until string completes (empty string or one char left), or if condition falls. First check for first and last char in the string, then if they are same do the same thing for a substring with first and last char removed, and so on...

for - loop

isPalindrome = (string) => {
  let strLen = Math.floor(string.length / 2);
  string = string.toLocaleLowerCase();

  for (let i = 0; i < strLen; i++) {
    if (string[i] !== string[strLen - i - 1]) {
      return false;
    }
  }
  return true;
}

//0.20 ms

for loop starts with the check for first char of the string and last char of the string. If it's equal, continue iterating through the string until the string reaches the center.

I like the first approach as it's clean and simple, but from a performance view, it gives us the worst result, where simple for loop is more than twice time faster.