Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
More Tests
export function mergeSort(array) {
let scratch = new Array(array.length);
_mergeSortImpl(array, 0, array.length-1, scratch);
return array;
}
function _mergeSortImpl(array, start, end, scratch) {
if(start >= end) { return; }
let middle = Math.floor((start + end) / 2);
_mergeSortImpl(array, start, middle, scratch);
_mergeSortImpl(array, middle+1, end, scratch);
_merge(array, start, middle, end, scratch);
}
function _merge(array, start, middle, end, scratch) {
for(let i = start; i <= end; ++i) {
scratch[i] = array[i];
}
let leftIdx = start;
let rightIdx = middle + 1;
let destIdx = start;
while(leftIdx <= middle && rightIdx <= end) {
if(scratch[leftIdx] < scratch[rightIdx]) {
array[destIdx] = scratch[leftIdx];
++leftIdx;
} else {
array[destIdx] = scratch[rightIdx];
++rightIdx;
}
++destIdx;
}
while(leftIdx <= middle) {
array[destIdx] = scratch[leftIdx];
++leftIdx;
++destIdx;
}
}
class Graph {
static Node = class Node {
constructor(weight, neighbors) {
this.weight = weight;
this.neighbors = neighbors;
}
}
// nodes is a map from node to a list of neighboring nodes.
constructor(nodes) { this.nodes = nodes; }
}
class PriorityQueue {
queue = [];
static Entry = class Entry {
constructor(item, priority) {
this.item = item;
this.priority = priority;
}
}
insert(item, priority) {
let i = 0;
while(this.queue[i] != null && this.queue[i].priority >= priority) {
++i;
}
this.queue.splice(i, 0, new PriorityQueue.Entry(item, priority));
return this.queue;
}
pop() {
return this.queue.pop();
}
toString() {
return `[${this.queue.map((x) => `(${x.priority}, ${x.item})`).join(', ')}]`;
}
}
let queue = new PriorityQueue();
queue.insert('A', 1);
queue.insert('B', 0);
queue.insert('C', 2);
queue.insert('D', 1);
queue.toString();
class PathFinder {
static walkBack(start, destination, visitedMap) {
let path = [];
let current = destination;
while (current != start) {
path.push(current);
current = visitedMap[current];
}
path.push(start);
return path.reverse();
}
static findPathBreadthFirst(graph, start, destination) {
let visitedToParent = {};
let frontier = [start];
let current;
while(frontier.length) {
current = frontier.shift();
if(current === destination) { break; }
for(let neighbor of graph.nodes[current].neighbors) {
if(visitedToParent[neighbor] == null) {
frontier.push(neighbor);
visitedToParent[neighbor] = current;
}
}
}
if(current != destination) {
return [];
} else {
return PathFinder.walkBack(start, destination, visitedToParent);
}
}
}
let graph = new Graph({
'A': new Graph.Node(1, ['B']),
'B': new Graph.Node(2, ['A', 'C', 'D']),
'C': new Graph.Node(3, ['A']),
'D': new Graph.Node(1, ['E', 'A']),
'E': new Graph.Node(2, ['B'])
});
let path = PathFinder.findPathBreadthFirst(graph, 'A', 'E');
import {mergeSort} from './algorithm.js'
console.log('-- START');
const SIZE = 10;
let array = new Array(SIZE);
for(let i = 0; i < SIZE; ++i) {
array[i] = Math.floor(Math.random() * 10);
}
array.slice(0)
mergeSort(array);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.