Algorithms with JavaScript

Published in

Analytics Vidhya

7 min readMay 9, 2020

A Day with JavaScript Algorithms - Milestone 2 (Day 6 - Week 2)

Today we will briefly discuss some simple and basic but mostly used Algorithms of any programming language including JavaScript. We will be covering - Mathematical Algorithms like Factorial and Fibonacci, Searching Algorithms like Linear Search and Binary Search, Sorting Algorithms like Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Quick Sort, and Heap Sort and also their implementations. So, let’s jump into this interesting article.

1. Factorial

In mathematics, the factorial of a positive integer n, denoted by n!, is the product of all positive integers less than or equal to n:

n! = n x (n - 1) x (n - 2) x (n - 3) x … x 3 x 2 x 1

For example,

5! = 5 x 4 x 3 x 2 x 1 = 120

Similarly,
6! = 720, 7! = 5040, 8! = 40320, 9! = 362880, 10! = 3628800

Except 0! = 1 (according to the convention for an empty product)

Iterative Factorial - JavaScript

Recursive Factorial - JavaScript

2. Fibonacci Number

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

I found this one interesting:
A tiling with squares whose side lengths are successive Fibonacci numbers

The Fibonacci spiral: an approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling;[4] this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13 and 21.

Iterative Factorial - JavaScript

Recursive Factorial - JavaScript

3. Linear Search

Linear Search or sequential search is a method for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched. Linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.

The Time Complexity of Linear Search is O(n) in worst case we're checking each element exactly once.

Linear Search - JavaScript

Why linear search is not efficient
There is no doubt that linear search is simple. But because it compares each element one by one, it is time-consuming and therefore not very efficient. If we have to find a number from, say, 1,000,000 numbers and that number is at the last position, a linear search technique would become quite tedious.

So we should also learn about bubble sort, quick sort, and other more efficient algorithms.

4. Binary Search

A simple search algorithm that searches a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array.

If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log n).

Binary Search — JavaScript

5. Bubble Sort

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Time Complexity of Bubble Sort:

Best - n

Average - n²

Worst - n²

Bubble Sort - JavaScript

6. Selection Sort

Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n²) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort.

Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Time Complexity of Selection Sort:

Best - O(n²)

Average - O(n²)

Worst - O(n²)

Selection Sort - JavaScript

7. Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands. It builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Time Complexity of Insertion Sort:

Best - O(n)

Average - O(n²)

Worst - O(n²)

Selection Sort - JavaScript

8. Merge Sort

Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output.

Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

An example of merge sort. First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.

A recursive merge sort algorithm used to sort an array of 7 integer values. These are the steps a human would take to emulate merge sort (top-down).

Time Complexity of Merge Sort:

Best - n log(n)

Average - n log(n)

Worst - n log(n)

Merge Sort - JavaScript

9. Quicksort

Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays

The steps are:

Pick an element, called a pivot, from the array.
Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values.

Time Complexity of Quick Sort:

Best - n log(n)

Average - log(n)

Worst - n²

Quick Sort - JavaScript

10. Heap Sort

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.