Skip to main content

Algorithm Guide

Types of Algorithms​

  • Sorting
    • arrange elements in a specific order
  • Search
    • locate a specific item or value in a collection
  • Graph
    • solve problems on graphs and networks
  • String
    • process and manipulate strings of characters
  • Computational geometry
    • solve problems in computational geometry
  • Dynamic programming
    • solve problems by breaking them into smaller sub-problems
  • Backtracking
    • incrementally building a solution and undoing when it is found to be invalid
  • Greedy
    • solve optimization problems by making the locally optimal choice at each step
  • Divide and conquers
    • solve problems by breaking them into smaller sub-problems and solving them recursively
  • Randomized
    • use randomness to solve problems, often more efficiently than deterministic algorithms.

Sorting​

  • Quicksort
    • O(n log n), divides & conquers.
  • Merge sort
    • O(n log n), divide & merge.
  • Radix sort
    • O(n+k), sorts by digits/character in temp. buckets. Fast but more memory.
  • Heapsort
    • O(n log n), uses heap data structure.
  • Introsort
    • O(n log n), hybrid of quicksort & heapsort.
  • Smoothsort
    • O(n log n), smooths unsorted sequences.
  • Shellsort
    • O(n log n) to O(n^2), diminishing increment sort.
  • Insertion sort
    • O(n^2) in the worst/avg and O(n) best-case (sorted), insert element into sorted sub-array.
  • Selection sort -
    • O(n^2), Select smallest element and swap with next position.
  • Bubble sort
    • O(n^2), repeatedly swaps adjacent elements.

Quicksort​

  • Quicksort is a popular sorting algorithm using a divide-and-conquer approach to sort an array or list.
  • The algorithm works by partitioning the array into two sub-arrays based on a "pivot" element, such that all elements less than the pivot are in one sub-array, and all elements greater than the pivot are in the other sub-array.
  • This process is repeated recursively for each sub-array until the entire array is sorted.
  • Quicksort is a highly efficient sorting algorithm that is widely used in practice, especially for large datasets.
  • Quicksort is commonly used in operating systems for sorting files and directories, as well as for managing memory and data structures.
  • Many sorting and searching algorithms and data structures, such as binary search trees and priority queues, use Quicksort as a building block or as a reference for comparison.
  • It has an average-case time complexity of O(n log n), which is faster than most other sorting algorithms, such as merge sort and insertion sort.
  • Quicksort is particularly well-suited for situations where the data is randomly distributed, as it tends to have good performance in such cases. It can also be used for data that is nearly sorted, although it may not be as efficient as some other algorithms in such cases.
  • However, Quicksort has a worst-case time complexity of O(n^2) if the pivot element is poorly chosen (e.g., if it is always the first or last element), which can happen with some input data. To mitigate this risk, various improvements have been proposed, such as choosing the pivot element randomly or using the "median of three" rule to choose a more balanced pivot.
function quickSort<T>(arr: T[], left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivotIndex = partition(arr, left, right);
    quickSort(arr, left, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, right);
  }
}

function partition<T>(arr: T[], left: number, right: number) {
  const pivotIndex = Math.floor((left + right) / 2);
  const pivotValue = arr[pivotIndex];
  let i = left;
  let j = right;

  while (true) {
    while (arr[i] < pivotValue) {
      i++;
    }

    while (arr[j] > pivotValue) {
      j--;
    }

    if (i >= j) {
      return j;
    }

    [arr[i], arr[j]] = [arr[j], arr[i]];
    i++;
    j--;
  }
}

Merge Sort​

  • Merge sort is a popular sorting algorithm that uses a divide-and-conquer approach to sort an array or list.
  • The algorithm works by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves into a single sorted array.
  • The merging step is performed using a temporary array or buffer.
  • Merge sort in 3 minutes, Merge Sort - Coding Algorithms Explained
  • Merge sort is both an optimial sort and a stable sorting algorithm, meaning that the relative order of equal elements in the input array is preserved in the output array.
  • Merge sort has a worst-case time complexity of O(n log n), which is faster than most other sorting algorithms, such as insertion sort and selection sort. It is particularly efficient for large datasets, as its time complexity is not affected by the input distribution (i.e., it always takes O(n log n) time to sort an array of size n).
  • Merge sort is well-suited for situations where stable sorting is required or where the input data is not amenable to other sorting algorithms.
  • It is commonly used in programming languages and libraries for sorting arrays and lists, and is also used in many other applications, such as data analytics and scientific computing.
function mergeSort<T>(arr: T[]): T[] {
  if (arr.length <= 1) {
    return arr;
  }

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

  return merge(mergeSort(left), mergeSort(right));
}

function merge<T>(left: T[], right: T[]): T[] {
  const result: T[] = [];

  let i = 0;
  let j = 0;

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

  while (i < left.length) {
    result.push(left[i]);
    i++;
  }

  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

Heapsort​

  • Heapsort is a sorting algorithm that uses a heap data structure to sort elements in a specific order.
  • The algorithm works by building a heap from the input array, and then repeatedly extracting the maximum (or minimum) element from the heap and placing it at the end of the array.
  • Animation of Heapsort
  • Heapsort has a worst-case time complexity of O(n log n), which is the same as other efficient sorting algorithms like Quicksort and Merge sort.
  • Heapsort is particularly useful for sorting data in external memory or in parallel, due to its ability to access data in a sequential manner.
  • Heapsort is commonly used in programming libraries and systems for sorting large datasets, and is also used in applications such as data analytics, scientific computing, and network routing.
function heapSort<T>(arr: T[]) {
  // Build max heap
  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, i, arr.length);
  }

  // Extract elements from heap in sorted order
  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, 0, i);
  }
}

function heapify<T>(arr: T[], root: number, size: number) {
  let largest = root;
  const left = 2 * root + 1;
  const right = 2 * root + 2;

  if (left < size && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < size && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest !== root) {
    [arr[root], arr[largest]] = [arr[largest], arr[root]];
    heapify(arr, largest, size);
  }
}

Bubble sort​

  • Bubble sort is a simple sorting algorithm that repeatedly iterates through a list or array, compares adjacent elements, and swaps them if they are in the wrong order.
  • The algorithm continues iterating through the list until no more swaps are needed.
  • Bubble sort is often used when the list is small and nearly sorted, as it has a simple implementation and can sort a small list efficiently.
  • It is also useful as a teaching tool for beginner programmers to understand sorting algorithms.
  • Use cases for bubble sort include sorting a deck of cards, sorting a small list of names, or sorting a small dataset for visualization purposes.
  • The time complexity of bubble sort is O(n^2), where n is the number of elements in the list.
  • This means that the time taken by the algorithm increases quadratically with the size of the list, which can make it inefficient for large datasets.
  • Bubble sort is a straightforward algorithm that can be easily understood and implemented by beginner programmers.
  • However, due to its O(n^2) time complexity, it is generally not used for large datasets and other sorting algorithms such as quicksort or mergesort are preferred.
  1. Define the bubble sort function with one parameter, the list or array to be sorted.
  2. Set a variable n to the length of the list.
  3. Start a loop that iterates from 0 to n-1:
    1. a. Start an inner loop that iterates from 0 to n-i-1:
      1. i. Compare the element at the current index with the next element.
      2. ii. If the current element is greater than the next element, swap them.
  4. If no swaps were made in the previous iteration, the list is sorted, and the algorithm can terminate.
  5. Otherwise, go back to step 3 and repeat the process until the list is sorted.

pseudo code

function bubbleSort(list):
    n = len(list)
    for i in range(n):
        for j in range(0, n-i-1):
            if list[j] > list[j+1]:
                list[j], list[j+1] = list[j+1], list[j]
    
    return list
export default function bubble_sort(arr: number[]): void {
  let swapped = true;
  while (swapped) {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        let temp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = temp;
        swapped = true;
      }
    }
  }
}

Searching​

* Binary search

  • O(log n), divides & conquers. Divide array in half until target found.
  • Interpolation search
    • O(log log n), uses formula. Estimate position based on range.
  • Exponential search
    • O(log n), doubles range. Double range until target found.
  • Fibonacci search
    • O(log n), divides range. Divide range according to Fibonacci sequence.
  • Jump search
    • O(sqrt(n)), skips elements. Jump ahead in fixed-size blocks.
  • Ternary search
    • O(log3 n), divides range into three parts.
  • Depth-first search (DFS)
    • O(V+E), Explore graph in depth-first manner.
  • Breadth-first search (BFS)
    • O(V+E), Explore graph in breadth-first manner.
  • A* search
    • O(b^d), uses heuristic to prioritize search.
  • Hill climbing search
    • O(?) , finds local maxima/minima. Move to neighbor with best heuristic value

  • Binary search is a search algorithm used to find a specific element in a sorted list or array.

  • It works by repeatedly dividing the search interval in half and eliminating the half where the target cannot be located until the target is found or the search interval is empty.

  • Binary search is often used when the list is sorted or partially sorted, as it takes advantage of the ordered nature of the list to efficiently find the desired element.

  • It is also useful for large datasets, where the time complexity of the algorithm can make a significant difference in performance.

  • Use cases for binary search include searching for a specific word in a dictionary or finding a specific value in a large dataset such as a stock market database.

  • The time complexity of binary search is O(log n), where n is the number of elements in the list.

  • This means that the time taken by the algorithm increases logarithmically with the size of the list, making it much faster than linear search for large datasets.

  • Binary search is a powerful algorithm that can significantly improve the performance of search operations on large datasets. It does require the list to be sorted or partially sorted, which can add additional complexity to the implementation.

Steps:

  1. Define the search function with two parameters, the sorted list or array to search and the target value to find.
  2. Set two variables, start and end, to represent the lower and upper bounds of the search interval. Set start to 0 and end to the length of the list minus 1.
  3. While start is less than or equal to end:
    1. a. Calculate the middle index of the current search interval by adding start and end, then dividing by 2 and rounding down to the nearest integer. Store the result in a variable called mid.
    2. b. If the target value is equal to the element at index mid, return mid.
    3. c. If the target value is less than the element at index mid, set end to mid minus 1.
    4. d. If the target value is greater than the element at index mid, set start to mid plus 1.
  4. If the target value is not found in the list, return a "not found" value or raise an appropriate exception.
function binarySearch(list, target):
    start = 0
    end = len(list) - 1
    
    while start <= end:
        mid = (start + end) // 2
        if list[mid] == target:
            return mid
        elif target < list[mid]:
            end = mid - 1
        else:
            start = mid + 1
    
    # If target is not found
    return -1
export default function bs_list(haystack: number[], needle: number): boolean {
    let left = 0;
    let right = haystack.length - 1;
    while (left <= right) {
        let middle = Math.floor((left + right) / 2);
        if (haystack[middle] === needle) {
            return true;
        } else if (haystack[middle] < needle) {
            left = middle + 1;
        } else {
            right = middle - 1;
        }
    }
    return false;
}