{{ MonaCodeLisa }}
{{ MonaCodeLisa }}

Follow

{{ MonaCodeLisa }}

Follow
Algorithms in JavaScript & TypeScript - Simple & Code Examples

Algorithms in JavaScript & TypeScript - Simple & Code Examples

{{ MonaCodeLisa }}'s photo
{{ MonaCodeLisa }}
·Feb 19, 2023·

16 min read

Table of contents

In this blog post, we will explore some of the most common algorithms used in Javascript and Typescript, and how they can be used to optimize your code and build more effective web applications.

Algorithms

Algorithms are fundamental to computer science and are a crucial tool for solving a wide range of problems efficiently. An algorithm is essentially a step-by-step process for solving a particular task or problem. It can be thought of as a recipe that tells a computer what to do to solve a specific problem. In the world of programming, algorithms are used for a variety of purposes, including data analysis, search and optimization, and even building user interfaces. With the rise of web development, algorithms have become a key part of modern web applications, making it easier to deliver faster and more efficient experiences to users.

Sorting Algorithms

Sorting algorithms are another essential concept in computer science that allow us to organize data in a specific order. There are various sorting algorithms, each with its unique approach to sorting data. Here's an overview of some common sorting algorithms:

  • Bubble Sort: This algorithm repeatedly swaps adjacent elements that are in the wrong order until the list is sorted.

  • Selection Sort: This algorithm selects the smallest element and swaps it with the first element, then selects the second smallest element and swaps it with the second element, and so on.

  • Insertion Sort: This algorithm builds the final sorted array one item at a time by repeatedly taking the next item and inserting it into the correct position in the sorted part of the array.

  • QuickSort: This algorithm divides the array into two sub-arrays based on a pivot element, then recursively sorts the sub-arrays.

  • MergeSort: This algorithm divides the array into two sub-arrays, recursively sorts each sub-array, and then merges the sorted sub-arrays.

Let's take a closer look at Bubble Sort with two code examples

Bubble Sort in JavaScript

function bubbleSort(array) {
  const len = array.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // Swap elements
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}

// Example usage
const myArray = [5, 3, 8, 4, 2];
const sortedArray = bubbleSort(myArray);
console.log(sortedArray); // Output: [2, 3, 4, 5, 8]

Bubble Sort in TypeScript

function bubbleSort(array: number[]): number[] {
  const len = array.length;

  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        // Swap elements
        const temp = array[j];
        array[j] = array[j + 1];
        array[j + 1] = temp;
      }
    }
  }

  return array;
}

// Example usage
const myArray: number[] = [5, 3, 8, 4, 2];
const sortedArray: number[] = bubbleSort(myArray);
console.log(sortedArray); // Output: [2, 3, 4, 5, 8]

In both examples, the bubbleSort function takes an array of numbers as an input parameter. It initializes the len variable to the length of the array and uses nested for loops to iterate over the array and compare adjacent elements.

Within the inner loop, the function compares the current element with the next element and swaps them if they are in the wrong order. The function continues this process until no more swaps are necessary, indicating that the array is sorted. The function then returns the sorted array.

The Bubble Sort algorithm has a time complexity of O(n^2) in the worst case, which means it can be inefficient for sorting large datasets. However, it is easy to implement and understand and can be a useful starting point for understanding sorting algorithms.

Searching Algorithms

Searching algorithms are a fundamental concept in computer science that allows us to efficiently locate specific data within a given set of information. There are different types of searching algorithms, each with its unique approach to searching for information. Here's a brief overview of some common searching algorithms:

  • Linear Search: This algorithm traverses a list of data elements sequentially until the target element is found or the end of the list is reached.

  • Binary Search: This algorithm is used on sorted arrays and repeatedly divides the search interval in half until the target element is found.

  • Jump Search: This algorithm is similar to binary search, but instead of dividing the array in half, it jumps to a specific index and then checks if the target element is greater than or less than the current element.

  • Interpolation Search: This algorithm is used on uniformly distributed arrays and estimates the position of the target element using its value and the values at the start and end of the array.

  • Exponential Search: This algorithm is used on sorted arrays and works by finding a range that the target element is likely to be in and then performing a binary search within that range.

Let's take a closer look at binary search with two code examples

Binary Search in JavaScript

function binarySearch(array, target) {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // Target not found
}

// Example usage
const myArray = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetIndex = binarySearch(myArray, 6);
console.log(targetIndex); // Output: 5

Binary Search in TypeScript

function binarySearch(array: number[], target: number): number {
  let low = 0;
  let high = array.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // Target not found
}

// Example usage
const myArray: number[] = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const targetIndex: number = binarySearch(myArray, 6);
console.log(targetIndex); // Output: 5

In both examples, the binarySearch function takes an array of numbers and a target number as input parameters. It then initializes two variables, low and high, to represent the start and end indices of the array. The function then enters a while loop that continues until low is greater than high, meaning the target element is not found.

Within the while loop, the function calculates the middle index using Math.floor((low + high) / 2) and compares the value at the middle index with the target value. If the middle element is equal to the target, the function returns the index of the middle element. Otherwise, it updates either low or high to narrow the search interval, depending on whether the middle element is less than or greater than the target. If the function exits the while loop without finding the target, it returns -1 to indicate that the target is not present in the array.

Pathfinding algorithms

Pathfinding algorithms are used to find the shortest path between two points in a graph or a grid. They are used in many real-world applications such as route planning in navigation systems, game AI, and network routing. Here are some commonly used pathfinding algorithms:

  • Breadth-first search (BFS): This algorithm starts at the root node and explores all the nodes at the current depth before moving on to the next level. It guarantees finding the shortest path in an unweighted graph.

  • Depth-first search (DFS): This algorithm starts at the root node and explores as far as possible along each branch before backtracking. It is not guaranteed to find the shortest path.

  • Dijkstra's algorithm: This algorithm calculates the shortest path between a source node and all other nodes in a weighted graph. It uses a priority queue to choose the next node to visit based on the shortest distance.

  • A* algorithm: This algorithm is an extension of Dijkstra's algorithm that uses a heuristic function to estimate the distance from the current node to the goal. It combines the actual cost of the path and the estimated cost to the goal to make a decision.

Breadth-first search algorithm in JavaScript

function BFS(startNode, endNode) {
  let queue = [startNode];
  let visited = new Set();
  visited.add(startNode);

  while (queue.length > 0) {
    let currentNode = queue.shift();

    if (currentNode === endNode) {
      // Found the path!
      return true;
    }

    currentNode.neighbors.forEach((neighbor) => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    });
  }

  // Path not found
  return false;
}

Breadth-first search algorithm in TypeScript

function BFS(startNode: Node, endNode: Node): boolean {
  let queue: Node[] = [startNode];
  let visited: Set<Node> = new Set();
  visited.add(startNode);

  while (queue.length > 0) {
    let currentNode = queue.shift();

    if (currentNode === endNode) {
      // Found the path!
      return true;
    }

    currentNode.neighbors.forEach((neighbor) => {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    });
  }

  // Path not found
  return false;
}

This code performs a Breadth-first search on a graph to find the shortest path from a starting node to an ending node. It uses a queue to keep track of the nodes to visit next and a set to keep track of visited nodes.

The code starts by initializing the queue with the start node and adding it to the visited set. It then enters a loop that continues until the queue is empty. In each iteration, it dequeues the next node to visit and checks if it is the end node. If it is, it returns true to indicate that the path has been found. Otherwise, it adds all of the node's unvisited neighbors to the queue and the visited set. If the loop completes without finding the end node, the function returns false.

Mathematical algorithms

Mathematical algorithms are used to solve problems and perform calculations in various fields of mathematics. These algorithms are designed to manipulate numbers, equations, and other mathematical objects to find solutions to problems.

Here are some popular Mathematical algorithms:

  • Factorial: An algorithm that computes the product of all positive integers up to a given number.

  • Fibonacci sequence: An algorithm that generates a sequence of numbers where each number is the sum of the two preceding ones.

  • Prime numbers: An algorithm that determines whether a given number is prime or not.

  • The greatest common divisor: An algorithm that finds the largest number that divides two given numbers without leaving a remainder.

Fibonacci sequence in JavaScript

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

// print the first 10 numbers in the Fibonacci sequence
for (let i = 0; i < 10; i++) {
  console.log(fibonacci(i));
}

This code generates the first 10 numbers in the Fibonacci sequence using a recursive function. The fibonacci function takes a number n as an argument and returns the n-th number in the Fibonacci sequence. The function uses recursion to compute the sum of the two preceding numbers in the sequence.

Fibonacci sequence in TypeScript

function fibonacci(n: number): number {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

// print the first 10 numbers in the Fibonacci sequence
for (let i = 0; i < 10; i++) {
  console.log(fibonacci(i));
}

This TypeScript code is equivalent to the previous JavaScript code and generates the first 10 numbers in the Fibonacci sequence using the same recursive function. The fibonacci function takes a number n as an argument and returns the n-th number in the Fibonacci sequence. The sequence is then printed to the console using a for loop.

Data compression algorithms

Data compression algorithms are used to reduce the size of digital data by encoding information more efficiently. By compressing data, it becomes easier and faster to transmit, store, and share.

Here are some popular Data compression algorithms:

  • Deflate algorithm: A widely used algorithm that combines the LZ77 algorithm and Huffman coding to compress data.

  • Huffman coding: An algorithm that uses variable-length codes to compress data by assigning shorter codes to more frequently occurring symbols.

  • Lempel-Ziv-Welch (LZW) compression: An algorithm that builds a dictionary of frequently occurring strings and replaces them with shorter codes.

Deflate compression in JavaScript

const zlib = require('zlib');

const data = 'hello world';

// compress the data using the deflate algorithm
zlib.deflate(data, (err, compressedData) => {
  if (err) throw err;

  // print the compressed data
  console.log('Compressed data:', compressedData.toString('base64'));
});

This code compresses the string "hello world" using the Deflate compression algorithm. The zlib.deflate method compresses the data and returns the compressed data as a buffer. The toString method is used to convert the buffer to a base64-encoded string, which is then printed to the console.

Deflate compression in TypeScript

import zlib from 'zlib';

const data: string = 'hello world';

// compress the data using the deflate algorithm
zlib.deflate(data, (err: Error | null, compressedData: Buffer) => {
  if (err) throw err;

  // print the compressed data
  console.log('Compressed data:', compressedData.toString('base64'));
});

This TypeScript code is equivalent to the previous JavaScript code and compresses the string "hello world" using the Deflate compression algorithm. The zlib.deflate method works the same as in the JavaScript example. The compressed data is then printed to the console as a base64-encoded string.

Cryptography algorithms

Cryptography algorithms are a set of mathematical functions that help in securing data and communications from unauthorized access. Cryptography algorithms convert plaintext data into ciphertext by using a key, making it difficult for anyone without the key to understand the message.

Here are some popular Cryptography algorithms:

  • Advanced Encryption Standard (AES): A widely used symmetric encryption algorithm that uses a fixed-length key to encrypt and decrypt data.

  • Caesar cipher: A simple substitution cipher where each letter in the plaintext is shifted a certain number of places down the alphabet.

  • RSA encryption: A public-key encryption algorithm that uses a pair of keys (public and private) to encrypt and decrypt data.

  • SHA-1 hashing: A cryptographic hash function that generates a fixed-size output (160 bits) from a variable-size input.

AES encryption in JavaScript

const crypto = require('crypto');

const secretKey = 'my_secret_key';
const data = 'hello world';

// create a cipher object using the secret key
const cipher = crypto.createCipher('aes-256-cbc', secretKey);

// update the cipher with the plaintext data
let encryptedData = cipher.update(data, 'utf8', 'hex');

// finalize the cipher with any remaining plaintext data
encryptedData += cipher.final('hex');

// print the encrypted data
console.log('Encrypted data:', encryptedData);

This code encrypts the string "hello world" using the AES-256-CBC encryption algorithm and a secret key. The crypto.createCipher method creates a cipher object with the specified algorithm and key. The cipher.update method updates the cipher with the plaintext data, and the cipher.final method finalizes the cipher with any remaining plaintext data. The encrypted data is then printed to the console.

AES encryption in TypeScript

import crypto from 'crypto';

const secretKey: string = 'my_secret_key';
const data: string = 'hello world';

// create a cipher object using the secret key
const cipher: crypto.Cipher = crypto.createCipheriv('aes-256-cbc', secretKey, crypto.randomBytes(16));

// update the cipher with the plaintext data
let encryptedData: string = cipher.update(data, 'utf8', 'hex');

// finalize the cipher with any remaining plaintext data
encryptedData += cipher.final('hex');

// print the encrypted data
console.log('Encrypted data:', encryptedData);

This TypeScript code is equivalent to the previous JavaScript code and encrypts the string "hello world" using the AES-256-CBC encryption algorithm and a secret key. The crypto.createCipheriv method creates a cipher object with the specified algorithm, key, and initialization vector (IV). The cipher.update and cipher.final methods work the same as in the JavaScript example. The encrypted data is then printed to the console.

Machine learning algorithms

Machine learning algorithms are computer programs that use statistical techniques to allow machines to improve their performance on a specific task as they are exposed to more data. These algorithms can be broadly categorized into three main types: supervised learning, unsupervised learning, and reinforcement learning.

Some common examples of machine learning algorithms are:

  • Linear Regression: A supervised learning algorithm used to predict continuous numerical values based on input variables.

  • K-Means Clustering: An unsupervised learning algorithm used to group similar data points together based on their similarity.

  • Decision Trees: A supervised learning algorithm used to classify data by recursively splitting it based on the value of certain features.

  • Neural Networks: A supervised learning algorithm used for complex tasks such as image recognition and natural language processing.

Linear regression in JavaScript:

// Define input and output data
const x = [1, 2, 3, 4, 5];
const y = [2, 4, 6, 8, 10];

// Define the regression model
const regression = require('regression');
const result = regression.linear(x.map((xi) => [xi]), y);

// Output the results
console.log(result.equation);

This code defines an input dataset x and output dataset y for a simple linear regression model. The regression library is used to fit the linear regression model to the data and the resulting equation is outputted to the console.

Linear regression in TypeScript:

// Define input and output data
const x: number[] = [1, 2, 3, 4, 5];
const y: number[] = [2, 4, 6, 8, 10];

// Define the regression model
import { linear } from 'regression';
const result = linear(x.map((xi) => [xi]), y);

// Output the results
console.log(result.equation);

This TypeScript code is nearly identical to the JavaScript code, but with added type annotations. The linear function is imported from the regression library instead of using the require statement.

Graph algorithms

Graph algorithms are a set of techniques and procedures that are designed to solve problems related to graphs, which are structures that consist of nodes (also known as vertices) and edges. These algorithms are used to analyze and manipulate graph data and are commonly used in computer science and various other fields such as physics, biology, and social network analysis.

Here are some examples of common Graph algorithms:

  • Depth-First Search (DFS): DFS is a traversal algorithm that visits all the vertices of a graph in depth-first order. It starts at a root node and explores as far as possible along each branch before backtracking.

  • Topological sorting: Topological sorting is used to arrange the vertices of a directed acyclic graph (DAG) in a linear order such that for every directed edge (u,v), vertex u comes before vertex v.

  • Kruskal's algorithm: Kruskal's algorithm is used to find the minimum spanning tree (MST) of a connected, weighted graph. It starts with an empty set of edges and gradually adds the edges with the smallest weights until all the vertices are connected.

  • Prim's algorithm: Prim's algorithm is another MST algorithm that starts with a single vertex and gradually adds the vertices with the smallest edge weights until all the vertices are connected.

Here are two equivalent code examples

Depth-First Search in JavaScript

// Define the graph as an adjacency list
const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
};

// Define the DFS function
function DFS(node, visited) {
  visited[node] = true;
  console.log(node);

  for (let i = 0; i < graph[node].length; i++) {
    const neighbor = graph[node][i];
    if (!visited[neighbor]) {
      DFS(neighbor, visited);
    }
  }
}

// Call the DFS function with the starting node
DFS(2, {});

Depth-First Search in TypeScript

// Define the graph as an adjacency list
const graph: {[key: number]: number[]} = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: [3]
};

// Define the DFS function
function DFS(node: number, visited: {[key: number]: boolean}): void {
  visited[node] = true;
  console.log(node);

  for (let i = 0; i < graph[node].length; i++) {
    const neighbor = graph[node][i];
    if (!visited[neighbor]) {
      DFS(neighbor, visited);
    }
  }
}

// Call the DFS function with the starting node
DFS(2, {});

In both examples, we first define the graph as an adjacency list. Then, we define the DFS function that takes a node and a visited object as arguments. The function marks the current node as visited, prints it to the console, and recursively calls itself on all unvisited neighbors. Finally, we call the DFS function with a starting node and an empty visited object. The output of this code will be the DFS traversal of the graph starting from node 2.


Algorithms are a vital component of computer science and software development. They enable programmers to solve complex problems and write efficient and scalable code. In this blog post, we explored the basics of algorithms and provided two code examples in JavaScript and TypeScript to illustrate how to implement a graph algorithm. By understanding the fundamental concepts behind algorithms and their implementation in JavaScript and TypeScript, you can enhance your problem-solving skills and build robust and innovative applications.

 
Share this