JavaScript Data Structures and Algorithms – Algorithm Implementations

Understanding data structures is essential, but it’s equally important to grasp various algorithms that allow you to manipulate and process data efficiently. In this article, we’ll explore some common algorithms and provide code examples in JavaScript to help you understand their implementations.

Sorting Algorithms

Sorting algorithms are crucial for organizing data. Two common sorting algorithms are Bubble Sort and Quick Sort. Let’s take a look at their implementations:

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

// Quick Sort
function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) left.push(arr[i]);
    else right.push(arr[i]);
  }

  return [...quickSort(left), pivot, ...quickSort(right)];
}

Search Algorithms

Search algorithms help find specific elements in a data structure. Two common search algorithms are Binary Search and Linear Search:

// Binary Search
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

// Linear Search
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Graph Algorithms

Graph algorithms are used to navigate and analyze data in graphs. One common algorithm is Depth-First Search (DFS). Here’s a simple implementation:

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) this.adjacencyList[vertex] = [];
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  depthFirstSearch(startVertex) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;

    (function dfs(vertex) {
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach((neighbor) => {
        if (!visited[neighbor]) return dfs(neighbor);
      });
    })(startVertex);

    return result;
  }
}

Dynamic Programming

Dynamic programming is a technique used to solve problems by breaking them into smaller subproblems. The Fibonacci sequence is a classic example. Here’s an implementation using dynamic programming:

function fibonacci(n) {
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

Conclusion

Algorithms are essential tools in computer science and software development. They enable you to solve a wide range of problems efficiently. Understanding algorithm implementations in JavaScript, as demonstrated above, will improve your ability to write optimized code and tackle complex challenges.