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 algorithmsCounting and radix sortSkipListSplay TreesTreapsBinary Heaps2-3-TreesAA TreesAVL TreesBinary Search TreesTreesLinked listsArrays for busy peopleAsymptotic Complexity
MergeSort and QuickSort
// Assuming that A[i...j-1] and A[j...k-1] are ordered,
// merge these subarrays into A[i...k-1]
function merge (A, i, j, k) {
let B = [];
let ii = i, jj = j;
while (ii < j && jj < k) {
if (A[ii] < A[jj]) B.push(A[ii++]);
else B.push (A[jj++]);
}
while (ii < j) B.push(A[ii++]);
while (jj < k) B.push(A[jj++]);
for (let ii = i; ii < k; ii++) A[ii] = B[ii-i]
}
// Sorts array A in ascending order
function mergeSort (A) {
function ms (i,k) {
if (k-i >= 2) {
let j = (i+k)>>1; // Middle index
ms (i,j);
ms (j,k);
merge (A,i,j,k)
}
}
ms (0,A.length)
}
{
let A = [0,5,4,1,2,3,6,7]
mergeSort(A)
return A
}
// Partitions A [i ... i+n-1] using A[i] as pivot;
// Returns the number of elements < pivot;
function partition (A, i, n) {
let x = A[i];
let m = 0;
for (let j = i+1; j < i+n; j++) {
if (A[j] < x) {
m++;
[A[j],A[i+m]] = [A[i+m],A[j]];
}
}
[A[i],A[i+m]] = [A[i+m],A[i]];
return m
}
// Sorts A in ascending order
function quickSort (A) {
function qs (i,n) {
if (n > 1) {
// Random pivot
let k = Math.trunc(Math.random()*n);
[A[i],A[i+k]] = [A[i+k],A[i]];
let m = partition (A, i, n);
qs (i,m);
qs (i+m+1, n-m-1);
}
}
qs (0, A.length)
}
{
let A = [5,0,4,1,2,3,6,7]
quickSort(A)
return A
}
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.
