Skip to content

Instantly share code, notes, and snippets.

@adamkorg
adamkorg / mergesort_r.cpp
Last active March 28, 2019 11:02
Merge sort (recursive)
#include <iostream>
#include <vector>
template<class T>
void merge(std::vector<T>& vals, int l, int m, int r) {
//iterate through both left and right partitions, selecting
//the lowest value of each comparision.
std::vector<T> out;
int i=l, j=m;
while(out.size() <= r-l) {
@adamkorg
adamkorg / mergesort_i.cpp
Created March 28, 2019 14:08
Merge sort (iterative)
#include <iostream>
#include <vector>
void merge(std::vector<int>& nums, int start, int chunk_size) {
//iterate through first partition (start -> start+chunk_size) while
//iterating through second partition and choose the smallest number
std::vector<int> result;
int mid = start + (chunk_size);
int merge_size = chunk_size*2;
for (int i=start,j=mid; result.size()<merge_size; ) {
@adamkorg
adamkorg / bubblesort.cpp
Created March 28, 2019 21:25
Bubble sort
#include <iostream>
#include <vector>
template <class T>
void bubble_sort(std::vector<T>& vals)
{
bool bMadeSwap = true;
while (bMadeSwap) {
bMadeSwap = false;
for (int i=0; i<vals.size()-1; i++) {
@adamkorg
adamkorg / quicksort_r.cpp
Created March 30, 2019 13:21
Quick Sort (recursive)
#include <iostream>
#include <vector>
template <class T>
int partition(std::vector<T>& vals, int l, int r) {
int i=l-1, j=r, v=vals[r];
for (;;) {
while (vals[++i] < v) ;
while (vals[--j] > v) if (j<1) break;
if (i>=j) break;
@adamkorg
adamkorg / quicksort_i.cpp
Created March 30, 2019 13:37
Quick Sort (iterative)
#include <iostream>
#include <vector>
#include <stack>
template <class T>
int partition(std::vector<T>& vals, int l, int r) {
int i=l-1, j=r, v=vals[r];
for (;;) {
while (vals[++i] < v) ;
while (vals[--j] > v) if (j<1) break;
@adamkorg
adamkorg / heapsort.cpp
Created March 31, 2019 18:20
Heap Sort
#include <iostream>
#include <vector>
template <class T>
class MinHeap
{
private:
std::vector<T> m_vals;
public:
@adamkorg
adamkorg / fibspiral.html
Created April 8, 2019 23:29
Fibonacci spiral
<html>
<body>
<canvas id="spiral" width="800" height="600">
</canvas>
<script>
function drawSpiral() {
var canvas = document.querySelector('#spiral');
var ctx = canvas.getContext('2d');
var i = 0, j=0, k=1;
var x = 200, y=200;
@adamkorg
adamkorg / bellmanford.cpp
Created April 11, 2019 22:39
Bellman Ford - Shortest path - vertex oriented
#include <iostream>
#include <vector>
#include <unordered_map>
struct edge {
int target;
int weight;
};
typedef std::unordered_multimap<int, edge> vertices;
@adamkorg
adamkorg / bellmanford2.cpp
Last active April 11, 2019 22:52
Bellman Ford - Shortest path - edge oriented
#include <iostream>
#include <vector>
struct edge {
int src;
int dst;
int weight;
};
std::vector<int> bellmanford(const std::vector<edge>& edges, int num_verts) {
@adamkorg
adamkorg / dijkstra.cpp
Last active April 14, 2019 21:55
Dijkstra algorithm - shortest path - simple n^2
#include <iostream>
#include <vector>
struct edge {
int src;
int dst;
int weight;
};
struct vertex {