Algorithms from beginners POV

Before writing this I took a minute and remembered how I imagined myself writing algorithms for optimizing data models which fastens up the data retrieval rate would look like. But by time I grew in this field I got to know that algorithms aren’t just code. These are some of the smart ways to tackle a problem and make data work faster

As ritual I will be covering few algo topics here which I use/have used on basis of my projects, paid gigs etc. The complexity of these algorithms will rise up gradually as the blog continues.
I hope you all know what is Linear Search ?
If not no worries this is the most common technique used by algorithms to lookup for a solution to the problem, take it as searching for word in dictionary before knowing "How to search words in dictionary" going through all the pages, but its okkay if the dictionary had only 10 to 15 pages but you would need a better and optimized way when there are literally 800+ pages

Binary Search

This is a fast and efficient algorithms but only for sorted array or list, works by repeatedly dividing in the search space in half, which reduces the number of elements to check. Starting at the middle of the array, it compares the target value to middle element. If the target matches, the search is complete.
If the target is smaller, it searches the left half, if larger the right half. This process continues until the value is found

For algorithms we will be talking more about time complexity. So Binary Search's time complexity is O(log_n) , making it faster than linear search for large sorted datasets

This is mainly used in searching databases, lookup tables, or implementing features like autocomplete. Here is an example of an api function which searches for a user by ID in a sorted list of users.

// Using Linear Search an going in sequential order
// it will take 10k iterations if we want to find the last user
const users = [
{ id: 1, name: "Sonita" },
{ id: 2, name: "Bonita" },
{ id: 3, name: "Aarav" },
// ... 10 thousand more more
];
function findUser(userId) {
  return users.find(user => user.id === userId); // O(n)
}

After using Binary Search Algorithm, for 10k users it just needs 14 comparisons at most to find any user

// ideal for static, sorted data like indexes or databases 
function binarySearch(users, userId) {
  let left = 0, right = users.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (users[mid].id === userId) return users[mid];
    if (users[mid].id < userId) left = mid + 1;
    else right = mid - 1;
  }
  return null;
}

This algorithm can also be applied in client side for searching an item in a sorted dropdown list

Depth First Search

The idea of DFS is starting with the root node and go as far down one branch as possible, all the way to the end.

After reaching the dead end we come back to the last visited node, this process of going back to the last visited node is called Backtracking[2]. We check if there are any unvisited nodes left. If there are, we explore those nodes next. If not, we backtrack again to the previous node. This process repeats until every node in the graph or tree has been visited[3].

The time complexity of DFS depends on the graph's structure. For a graph with Vvertices (nodes) and E edges (connections), using a list of connected nodes. DFS takes O(V + E) time. This because it visits each vertex once and checks all edges to explore neighbors. It’s fast for most graphs, especially sparse ones like social networks, as it only processes the actual connections

const comments = [
  { id: 1, text: "Great!", replies: [{ id: 2, text: "Thanks!" }] },
  { id: 3, text: "Cool", replies: [] },
];
function renderComments() {
  let html = "";
  for (let comment of comments) {
    html += `${comment.text}`;
    if (comment.replies) {
      for (let reply of comment.replies) {
        html += `${reply.text}`;
      }
    }
  }
  return html;
}

One of the OSS issue on which I worked was related to ui rendering nested comments inefficiently with manual looping, which struggled with deep nesting

My Pull request for the same issue, used DFS. I have attached the full anatomy here

/*
 * Ideal for exploring all paths, detecting cycles, or solving
 * problems requiring exhaustive search.
 *
 * "comments" is an array of comment objects.
 * "depth" is an optional parameter indicating how deep in the
 * reply hierarchy we are. It starts at 0 for the top-level comment.
 */
function renderComments(comments, depth = 0) {
  /*
   * This will hold the final HTML output that gets returned.
   */
  let html = "";

  /*
   * Iterate through each comment in the comments array.
   */
  for (let comment of comments) {

    /*
     * Append the current comment's text to the HTML string.
     */
    html += `${comment.text}`;

    /*
     * If the current comment has replies, recursively render
     * those replies and increase the depth by 1.
     *
     * This is where the recursive traversal happens:
     * each reply can itself contain more replies.
     */
    if (comment.replies) {
      html += renderComments(comment.replies, depth + 1);
    }
  }

  /*
   * Return the complete HTML generated from this level
   * and all of its nested replies.
   */
  return html;
}

This can also be used for detecting cycles in dependency graphs for building package managers.

Breadth First Search

In Breadth first search it explores graphs differently. Instead of diving deep like DFS, BFS visits all nodes at the current "level" before moving to next.

Starting from a chosen node, it explores all its immediate neighbors first, then their neighbors, and so on. This makes BFS ideal for finding the shortest path in unweighted graphs for exploring nodes closer to starting point.

For the time complexity part we can say its similar to DFS which is O(V +E) but the only difference is, BFS uses queue to track nodes, ensuring it explores closer nodes first, which is why its great for finding shortest paths in unweighted graphs, like in navigation apps or GPS

Code Dissection of Friends graph is written below

const users = {
  'Sonita': ['Aarav', 'Charlie'],
  'Bonita': ['Vegeta', 'David'],
  'Gojita': ['Vegito'],
  'Majin Buu': ['Mr. Satan']
};

/*
 * Find the shortest connection between two users.
 *
 * We use BFS here because we want to find the minimum number
 * of connections (steps) needed to get from user1 to user2.
 */
function findConnection(user1, user2) {

  /*
   * Start with user1 at a connection distance of 0.
   *
   * Each item in the queue is stored as:
   * [user, distance_from_user1]
   */
  const queue = [[user1, 0]];

  /*
   * Keep track of users we have already visited.
   *
   * This prevents us from visiting the same user multiple
   * times and getting stuck in a cycle.
   */
  const visited = new Set([user1]);

  /*
   * Main BFS loop.
   *
   * We continue exploring users until the queue becomes empty.
   */
  while (queue.length) {

    /*
     * Remove the first item from the queue.
     *
     * "user" represents the person we are currently exploring.
     * "distance" represents how many connections away this user
     * is from user1.
     */
    const [user, distance] = queue.shift();

    /*
     * If the current user is the target user, we have found
     * the shortest path.
     *
     * Because BFS explores level by level, the first time we
     * reach user2, this distance is guaranteed to be minimal.
     */
    if (user === user2) return distance;

    /*
     * Explore every friend of the current user.
     *
     * If we haven't visited a friend yet:
     *
     * 1. Mark the friend as visited.
     * 2. Add the friend to the queue.
     * 3. Increase the distance by 1 because the friend is
     *    one connection further away from user1.
     */
    for (let friend of users[user]) {
      if (!visited.has(friend)) {
        visited.add(friend);
        queue.push([friend, distance + 1]);
      }
    }
  }

  /*
   * If the queue becomes empty without finding user2,
   * there is no connection between user1 and user2.
   *
   * Return -1 to indicate that the target was not found.
   */
  return -1;
}

Insertion Sort Algorithm

Insertion sort is a simple sorting algorithm that builds a sorted array one element at a time.

Starting with the second element, insertion sort compares it to the previous ones, shifting larger elements right until it finds the right spot to "insert" the element. This process repeats for each element until the entire array is sorted. Works well for small datasets or nearly sorted lists, like organizing a short list of names or numbers.

The time complexity of Insertion Sort depends on the array size and its initial order. For an array with n elements, the worst-case time complexity is O(n^2) as each element may need to be compared and shifted against all previous elements, like when the array is reverse-sorted. In the best case, such as a nearly sorted array, it runs in O(n) time, as each element requires minimal comparisons and shifts. This makes Insertion Sort efficient for small or nearly sorted datasets but less ideal for large, unsorted lists compared to faster algorithms like Quick Sort.

function insertionSort(arr) {
  // Start from the second element (i = 1), since the first element is considered "sorted"
  for (let i = 1; i < arr.length; i++) {
    
    // 'key' is the current element we want to insert into the sorted part of the array
    let key = arr[i];

    // 'j' marks the end of the sorted portion (just before the current element)
    let j = i - 1;

    //Move elements of arr[0..i-1], that are less than 'key.time', one position ahead
    //sort in descending order based on 'time' property
    while (j >= 0 && arr[j].time < key.time) {
      // Shift the element to the right
      arr[j + 1] = arr[j];
      j--; // Move one step back in the array
    }

    // Insert the 'key' in its correct position
    arr[j + 1] = key;
  }

  // Return the sorted array
  return arr;
}

Merge Sort Algorithm

Its a reliable sorting algorithm which uses a divide and conquer approach to sort arrays efficiently.

It works by splitting the array into two halves, sorting each half recursively, and then merging the sorted halves back together to create a fully sorted array. Its stable meaning, it preserves the relative order of equal elements, and is ideal for large datasets, like sorting customer records or database entries, due to its consistent performance.

Lets talk a little about the time complexity here, merge sort has a time complexity of O(nlogn) in all cases from best, average to worst. For example lets take the above figure which is [4, 2, 5, 1, 8, 3, 7, 6] here n = 8 elements and for n = 8 elements it takes log_n8 = 3 levels of division (8 --> 4 pairs --> 2 groups of 4 --> 1 group of 8). Our figure starts with four groups of two which is part of this process.

At each level, all n elements are merged. Merging two sorted lists compares and combines elements in linear time. Merging four pairs ([4,2], [5,1], [8,3], [7,6]) into two groups takes about 8 comparisons total merging two groups ([1,2,4,5], [3,6,7,8]) into one takes another 8 comparisons.

The O(n log n) complexity holds because the number of divisions is logarithmic logn and each merge step scales linearly with n. Unlike insertion sort's O(n^2)(upto 64 operations for n = 8)

BEFORE

The API gets session data from the DB. Uses .sort() which may be unstable or optimized differently depending on V8 engine. So we get less control over performance in large datasets

app.get('/api/sessions/sorted', async (req, res) => {
  const sessions = await db.getUserSessions(); // returns array like [120, 30, 45, 60]
  
  // Using built in sort (not always stable or predictable)
  const sorted = sessions.sort((a, b) => a - b);

  res.json({ sorted });
});

After using Merge Sort

After using our own implementation of merge sort and replacing it with built in sort, it helped with performance tuning and custom rules which can handling large logs or preprocessing logs offline

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

module.exports = { mergeSort };


// on different file we can call the function and use it
const { mergeSort } = require('../utils/mergeSort');

app.get('/api/sessions/sorted', async (req, res) => {
  const sessions = await db.getUserSessions();

  const sorted = mergeSort(sessions);

  res.json({ sorted });
});

Quick Sort Algorithm

This uses the same strategy as Merge Sort algorithm which is divide and conquer strategy to sort arrays. But it works by picking a "pivot" element, partitioning the array so that element smaller than the pivot are on its left and larger ones on its right, then recursively sorting the left and right sub-arrays.

Quick Sort is fast and widely used for large datasets, like sorting student grades or product lists, due to its average-case speed.

For an array with n elements, Quick Sort’s time complexity is O(nlogn) on average, making it very fast for most cases. It divides the array into two parts around a pivot, ideally halving the problem size each time, requiring log n levels and n comparisons per level. sorting an array of 8 elements takes about 24 operations (8 * log 8). In the worst case, like a sorted or reverse-sorted array with a poor pivot choice, it can degrade to O(n²), but this is rare with good pivot strategies.

Something very important is choosing a good pivot for efficiency as it effects how evenly the array is split. Here are some common steps you can include while choosing one

BEFORE

The best way I learned quick sort algorithm was by implementing it in a e-commerce api in which products were sorted by price, at first I thought using .sort() would be but NVM XDD. It was simple and short but lacked control and it can't handle complex logic lick preprocessing, side effects, or tracing steps for debugging

app.get('/api/products/sorted', async (req, res) => {
  const products = await db.getProducts(); // [{ name: "Shoes", price: 80 }, ...]

  const sorted = products.sort((a, b) => a.price - b.price);

  res.json({ sorted });
});

AFTER

After learning and implementing my own Quick Sort to sort products by price, this let me add debug logs, skip invalid prices, add thresholds or filtering inline, or customize order (ascending / descending)

function quickSortProducts(arr, ascending = true) {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = [];
  const right = [];

  for (let i = 0; i < arr.length - 1; i++) {
    if (!arr[i].price) continue; // skip if price is missing

    if (ascending ? arr[i].price < pivot.price : arr[i].price > pivot.price) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

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

module.exports = { quickSortProducts };

const { quickSortProducts } = require('../utils/quickSortProducts');

app.get('/api/products/sorted', async (req, res) => {
  const products = await db.getProducts();

  const order = req.query.order || 'asc'; // ?order=desc
  const sorted = quickSortProducts(products, order === 'asc');

  res.json({ sorted });
});

I wanted to add greedy algorithm and DP but that would be an overkill for this blog, these are searching and sorting algorithms which is mainly used during development
Hope I was able to add few value to your today's learning :)