Practicing some algorithms

algorithms.md

Sorting

Mergesort

export default function mergesort(array) {
  if (array.length <= 1) { return array; }
  const halfIndex = Math.floor(array.length / 2);
  const left = array.splice(0, halfIndex);
  return merge(mergesort(left), mergesort(array));
}

function merge(a1, a2) {
  const result = [];
  while (a1.length > 0 && a2.length > 0) {
    result.push( a1[0] < a2[0] ? a1.shift() : a2.shift() );
  }
  result.push.apply(result, a1);
  result.push.apply(result, a2);
  return result;
}

Quicksort

export default function quicksort(array) {
  if (array.length === 0) { return array; }

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

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

  // return quicksort(left).concat(pivot, quicksort(right));
  return [ ...quicksort(left), pivot, ...quicksort(right) ]
}

Or

export default function quicksort(array) {
  return quicksortHelper(array, 0, array.length - 1);
}

function quicksortHelper(array, low, high) {
  if (high > low) {
    const p = partition(array, low, high);
    quicksortHelper(array, low, p - 1);
    quicksortHelper(array, p + 1, high);
  }
  return array;
}

function partition(array, low, high) {
  let p = high;
  let firsthigh = low;
  for (let i = low; i < high; ++i) {
    if (array[i] < array[p]) {
      swap(array, i, firsthigh);
      ++firsthigh;
    }
  }
  swap(array, p, firsthigh);
  
  return firsthigh;
}

function swap(array, i, j) {
  [ array[i], array[j] ] = [ array[j], array[i] ];
}

Graph Traversal

The following use a TraversalNode class to represent the state and process of traversing the graph:

class TraversalNode {
  constructor(value) {
    this.value = value;
    this.entered = null;
    this.exited = null;
  }
  
  get discovered() { return this.entered != null; }
  
  get processed() { return this.exited != null; }
  
  discoveredAt(time) {
    this.entered = time;
  }
  
  processedAt(time) {
    this.exited = time;
  }
  
  toString() { return this.value; }
}

They expect input in the form

{
  vertices: [ 'a', 'b', 'c', 'd' ],
  edges: {
    0: [ 3 ],
    1: [],
    2: [ 3 ],
    3: [ 0, 1, 2, 3 ]
  }
}

They also accept an options hash of the form

{
  startIndex: 2,
  processVertexEarly(traversalNode) { ... },
  processVertexLate(traversalNode) { ... },
  processEdge(fromNode, toNode) { ... }
}

Breadth-First Search

export default function breadthFirstSearch({ vertices, edges }, opts = {}) {
  const startIndex = opts.startIndex || 0;
  const processVertexEarly = opts.processVertexEarly || noop;
  const processVertexLate = opts.processVertexLate || noop;
  const processEdge = opts.processEdge || noop;

  const traversal = vertices.map(function(vertex) {
    return new TraversalNode(vertex);
  });
  let time = 0;
  traversal[startIndex].discoveredAt(time++);
  const toProcess = [ startIndex ];
  
  while (toProcess.length > 0) {
    const currentIndex = toProcess.shift();
    const currentStep = traversal[currentIndex];
    processVertexEarly(currentStep);
    (edges[currentIndex] || []).forEach(function(toIndex) {
      const toStep = traversal[toIndex];
      processEdge(currentStep, toStep);
      if (!toStep.discovered) {
        toStep.discoveredAt(time++);
        toProcess.push(toIndex);
      }
    });
    processVertexLate(currentStep);
    currentStep.processedAt(time++);
  }
  
  return traversal;
}

function noop() {}

Depth-First Search

export default function depthFirstSearch({ edges, vertices }, processVertex = function() {}) {
  const processed = Array.apply(null, Array(vertices.length)).map(() => false);
  dfsHelper(edges, vertices, processVertex, 0, new Array(edges.length));
}

function dfsHelper(edges, vertices, processVertex, currentIndex, processed) {
  processVertex(vertices[currentIndex]);
  processed[currentIndex] = true;

  edges.forEach(function({ from, to }) {
    if (from === currentIndex && !processed[to]) {
      dfsHelper(edges, vertices, processVertex, to, processed);
    }
  });
}