Computer Graphics & Visualization @ufrj.br
Point k-d trees with queriesHash table with open addressing and double hashingHash table with separate chainingPoint k-d treesOmohundro balltree construction algorithmsMergeSort and QuickSortSkipListSplay TreesTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
Counting and radix sort
// Returns A sorted in ascending order of keys, where the key value of A[i] is given by f(A[i]).
// Assumes f() returns integer values from 0 to some (small) k.
function countSort (A, k, f = x => x) {
let R = [], B = [];
let n = A.length;
for (let i = 0; i < k; i++) R[i] = 0;
for (let x of A) R[f(x)]++;
for (let i = 1; i < k; i++) R[i] += R[i-1];
for (let i = n-1; i >= 0; i-- ) {
let j = --R[f(A[i])];
B [j] = A[i]
}
return B
}
countSort ([5,4,3,2,1,0,0], 6)
countSort ([1,15,12,13,19,23,40, 14,12],10, x=>x%10)
countSort (countSort ([1,15,12,13,19,23,40, 14,12],10, x=>x%10), 10, x=>~~(x/10))
// Returns array A sorted in ascending order. It is assumed that A has positive integer
// numbers, with up to d bytes
function radixSort (A, d) {
for (let i = 0; i < d; i++) {
let f = x => x>>(8*i) & 0xff;
A = countSort (A, 256, f)
}
return A
}
radixSort([1029, 3141, 13123, 5248, 843, 22, 19813, 32677, 9], 2)
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
