Skip to content

Instantly share code, notes, and snippets.

@bernhardfritz
Created March 10, 2023 18:59
Show Gist options
  • Select an option

  • Save bernhardfritz/c165238765751acc81778b8615c47f19 to your computer and use it in GitHub Desktop.

Select an option

Save bernhardfritz/c165238765751acc81778b8615c47f19 to your computer and use it in GitHub Desktop.
import p8g, {
background,
createCanvas,
height,
line,
noSmooth,
random,
} from 'https://unpkg.com/p8g.js';
const gaps = [701, 301, 132, 57, 23, 10, 4, 1];
const shellSort = (a) => {
const n = a.length;
for (const gap of gaps) {
for (let i = gap; i < n; i++) {
const temp = a[i];
let j;
for (j = i; j > gap - 1 && a[j - 1] > temp; j -= gap) {
a[j] = a[j - gap];
}
a[j] = temp;
}
}
return a;
};
const fisherYatesShuffle = (a) => {
const n = a.length;
for (let i = 0; i < n - 2; i++) {
const j = Math.floor(random(i, n));
[a[i], a[j]] = [a[j], a[i]];
}
return a;
};
function* makeIterator(fn, a) {
const steps = [];
const handler = {
set(target, p, newValue) {
steps.push([p, newValue]);
target[p] = newValue;
return true;
},
};
const proxy = new Proxy([...a], handler);
fn(proxy);
for (const step of steps) {
yield step;
}
}
const n = 100;
const sorted = [...Array(n).keys()];
let it, a;
const init = () => {
const unsorted = fisherYatesShuffle(sorted);
it = makeIterator(shellSort, unsorted);
a = [...unsorted];
};
init();
p8g.draw = () => {
background(255);
noSmooth();
a.forEach((y, x) => {
line(x, height, x, height - y);
});
const { value, done } = it.next();
if (done) {
init();
} else {
const [x, y] = value;
a[x] = y;
}
};
createCanvas(n, n);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment