Sorting Algorithms and Data Structures for JavaScript
1. Sorting Algorithms 1.1 Bubble Sort Array function sort(arr) { const len = array_length(arr); for (let i = len-1 ; i > 0 ; i = i – 1) { for (let j = 0 ; j < i ; j = j + 1 ) { if (arr[j] > arr[j+1]) { let temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } else { } } } return arr; }
1.2 Selection Sort Array function selection_sort(A) { const len = array_length(A);
for (let i = 0; i < len – 1; i = i + 1) {
let j_min = i; for (let j = i + 1; j < len; j = j + 1) { if (A[j] < A[j_min]) { j_min = j; } else {} }
if (j_min !== i) { swap(A, i, j_min); } else {} } }
function swap(A, x, y) { const temp = A[x]; A[x] = A[y]; A[y] = temp; }
1.3 Insertion Sort Array function insertion_sort(A) { const len = array_length(A);
for (let i = 1; i < len; i = i + 1) { let j = i – 1; while (j >= 0 && A[j] > A[j + 1]) { swap(A, j, j + 1); j = j – 1; } } }
function swap(A, x, y) { const temp = A[x]; A[x] = A[y]; A[y] = temp; }
1.4 Insertion Sort Array Without Swap Function function insertion_sort2(A) { const len = array_length(A);
for (let i = 1; i < len; i = i + 1) { const x = A[i]; let j = i – 1; while (j >= 0 && A[j] > x) { A[j + 1] = A[j]; // shift right j = j – 1; } A[j + 1] = x; } }
1.5 Merge Sort Array function merge_sort(A) { merge_sort_helper(A, 0, array_length(A) – 1); }
function merge_sort_helper(A, low, high) { if (low < high) { const mid = math_floor((low + high) / 2); merge_sort_helper(A, low, mid); merge_sort_helper(A, mid + 1, high); merge(A, low, mid, high); } else {} }
function merge(A, low, mid, high) { const B = []; let left = low; let right = mid + 1; let Bidx = 0;
while (left <= mid && right <= high) { if (A[left] <= A[right]) { B[Bidx] = A[left]; left = left + 1; } else { B[Bidx] = A[right]; right = right + 1; } Bidx = Bidx + 1; }
while (left <= mid) { B[Bidx] = A[left]; Bidx = Bidx + 1; left = left + 1; } while (right <= high) { B[Bidx] = A[right]; Bidx = Bidx + 1; right = right + 1; }
for (let k = 0; k < high – low + 1; k = k + 1) { A[low + k] = B[k]; } }
1.6 Insertion Sort List function insert(x, xs){ return is_null(xs) ? list(x) : x <= head(xs) ? pair(x, xs) : pair(head(xs), insert(x, tail(xs))); }
function insertion_sort(xs){ return is_null(xs) ? xs : insert(head(xs), insertion_sort(tail(xs)); }
1.7 Merge Sort List function take(xs, n){ return is_null(xs) ? null : n === 0 ? null : pair(head(xs), take(tail(xs), n-1)); }
function drop(xs, n){ return is_null(xs) ? null : n === 0 ? xs : drop(tail(xs), n-1); }
function merge(xs, ys) { if (is_null(xs)){ return ys; } else if (is_null(ys)){ return xs; } else if (head(xs) <= head(ys)){ set_tail(xs, merge(tail(xs), ys)); return xs; } else { set_tail(ys, merge(xs, tail(ys))); return ys; } }
function merge_sort(xs){ if(is_null(xs)||is_null(tail(xs))){ return xs; } else { const mid = math_floor(length(xs)/2); return merge(merge_sort(take(xs, mid)), merge_sort(drop(xs, mid))); } }
1.8 Quick Sort List function partition(xs, p) { return is_null(xs) ? pair(null, null) : length(xs) <= 1 ? head(xs) : pair(filter(x => x <= p, xs), filter(y => y > p, xs)); }
function quicksort(xs) { const len = length(xs);
if (is_null(xs)) { return null; } else if (len === 1) { return xs; } else if (len === 2) { if (head(xs) > head(tail(xs))) { return list(head(tail(xs)), head(xs)); } else { return xs; } } else { const sortie = partition(tail(xs), head(xs); return append(quicksort(head(sortie)), pair(head(xs), quicksort(tail(sortie)))); } }
1.9 Selection Sort List function smallest(xs){ let smallest = head(xs); for (let k = 1; k < length(xs); k = k + 1){ if (list_ref(xs, k) < smallest){ smallest = list_ref(xs, k); } else {} } return smallest; }
function selection_sort(xs){ if (is_null(xs)) { return xs; } else { return pair(smallest(xs), selection_sort(remove(smallest(xs), xs))); } }
2. Cancer Programs 2.1 Permutations function permute(lst) { return is_null(lst) ? list(null) : accumulate(append,null,map(x => map(p => pair(x,p), permute(remove(x,lst))) ,lst)); }
2.2 Combinations function combinations(xs, n) { if ((is_null(xs) && n !== 0 )|| n < 0) { //if list becomes null, and other failure conditions return null; } else if (n === 0) { return list(null); //list(null) is to allow map to work on it, bc map does not work on null, which is an empty list } else { const s1 = combinations(tail(xs), n-1); //decrease counter const usent = combinations(tail(xs), n); //does not decrease counter const use = map(y=>pair(head(xs), y), s1); //maps the used head over all the subsequent combos generated return append(use, usent); } }
3. Big Brain Solutions 3.1 Using helper functions to generate streams function make_slow(a,b){ return b <= 0 ? make_slow(a+1, a+1) //this one immediately runs : () => make_slow(a, b-1); //this one does not run immediately as it is hidden behind a function }
3.2 Rotating a matrix clockwise //first, do a matrix transpose using swaps //iterating through the diagonal of the array //you swap stuff along the row and column you are pointing at //something like cofactor expansion but along the diagonal
for (let r = 0; r < n; r = r + 1){ //the below part sets the thing to start at diagonal for (let c = r + 1; c < n; c = c + 1){ swap(r, c, c, r); //using swap function declared below //this swaps the position with its mirror image along the diagonal } }
//then reverse the array, bc of reasons const half_n = math_floor(n/2); for (let r = 0; r < n; r = r + 1){ for (let c = 0; c < half_n; c = c + 1){ swap(r, c, r, n – 1 – c); //remember, arrays start from 0; } }
3.3 Quick Hull //assume all constants have been predeclared function process_half(A, B, pts){ if (is_null(pts)){ return null; } else { const C = furthest(A, B, pts); const rest = remove(C, pts);
const R1 = head(partition(A, C, rest)); const R2 = head(partition(C, B, rest));
return pair(C, append(process_half(A, C, R1), process_half(C, B, R2))); } }
4. Array Processing 4.1 Swap function swap(arr, r1, c1, r2, c2){ let temp = arr[r1][c1]; arr[r1][c1] = arr[r2][c2]; arr[r2][c2] = temp; }
5. Metacirculator ok boys lets get started
1. Principles of Metacirculator we have 3 basic principles here:
1. for shit that doesnt create a new frame (e.g. declaring functions, evaluating arguments): evaluate the thing in the same environment as usual
2. for shit that creates new frames (e.g. evaluating function calls): get body get param names get param values extend the function environment with the new param names and param values then evaluate the body in the extended environment, like so:
from apply(fun, arg) //first, we get all the shit we need const body = function_body(fun); //the function body
const locals = local_names(body); //get the names of the arguments [1]
const names = insert_all(function_parameters(fun), //the param names locals);
const temp_values = map(x => no_value_yet, locals); //then map no_value_yet to all the names in [1]
const values = append(args, temp_values); //the param values (assigning arguments to the names)
const result = evaluate(body, //this is the body of the function extend_environment( //extending the function environment with param names and values names, //refers to the param names values, //refers to the param values function_environment(fun) //refers to the environment created by the function ));
2. Everything is a Bunch of Eval and Apply Cycles. 2.1 When you apply, you have to evaluate the function body in the function environment 2.2 When you evaluate, you have to apply any functions seen – which creates a new function environment
//bro, my brain is expanding.