gnomeSort = {
let input = makeInput();
let pos = 0;
yield* pauser(display(input, {pos, immediate: true}));
while (pos < input.length) {
if (pos == 0 || input[pos] >= input[pos - 1]) {
pos = pos + 1;
} else {
let a = input[pos];
let b = input[pos - 1];
input[pos] = b;
input[pos - 1] = a;
pos = pos - 1;
yield display(input, {pos, highlight:new Set([pos, pos-1])});
}
}
yield display(input, {done: true});
}
bubbleSort = {
let input = makeInput();
yield* pauser(display(input, { immediate: true }));
for (let i = 0; i < input.length; i++) {
for (let j = 1; j < input.length; j++) {
if (input[j - 1] > input[j]) {
let a = input[j];
let b = input[j - 1];
input[j] = b;
input[j - 1] = a;
yield display(input, {pos: i, highlight:new Set([j, j-1])});
}
}
}
yield display(input, {done: true});
}
shellSort = {
let input = makeInput();
yield* pauser(display(input, { immediate: true }));
let gaps = [1];
for (let i = 0; i < Math.floor(Math.sqrt(input.length)); i++) {
gaps.push(Math.pow(i, 2) + 1);
}
gaps.reverse();
for (let gap of gaps) {
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already in gapped order
// keep adding one more element until the entire array is gap sorted
for (let i = gap; i < input.length; i += 1) {
// add a[i] to the elements that have been gap sorted
// save a[i] in temp and make a hole at position i
let temp = input[i];
let j;
// shift earlier gap-sorted elements up until the correct location for a[i] is found
for (j = i; j >= gap && input[j - gap] > temp; j -= gap) {
input[j] = input[j - gap]
yield display(input, {pos: i, highlight:new Set([j, j-gap])});
}
// put temp (the original a[i]) in its correct location
input[j] = temp
}
}
yield display(input, {done: true});
}
cocktailSort = {
let input = makeInput();
yield* pauser( display(input, { immediate: true }));
let swapped = false;
do {
swapped = false;
let i;
for (i = 0; i < input.length - 1; i++) {
if (input[i] > input[i + 1]) {
let a = input[i];
let b = input[i + 1];
input[i] = b;
input[i + 1] = a;
swapped = true;
yield display(input, {pos: i, highlight:new Set([i, i+1])});
}
}
if (!swapped) {
break;
}
swapped = false;
for (i = input.length - 1; i > 0; i--) {
if (input[i] > input[i + 1]) {
let a = input[i];
let b = input[i + 1];
input[i] = b;
input[i + 1] = a;
swapped = true;
yield display(input, {pos: i, highlight:new Set([i, i+1])});
}
}
} while (swapped);
yield display(input, {done: true});
}
selectionSort = {
let input = makeInput();
yield* pauser(display(input, { immediate: true }));
for (let j = 0; j < input.length; j++) {
let min = j;
for (let i = j + 1; i < input.length; i++) {
if (input[i] < input[min]) {
min = i;
}
}
if (min !== j) {
let a = input[j];
let b = input[min];
input[j] = b;
input[min] = a;
yield display(input, {pos: j, highlight:new Set([min, j])});
}
}
yield display(input, {done: true});
}
quickSort = {
let input = makeInput();
yield* pauser(display(input, { immediate: true }));
function* quicksort(left, right) {
if (left < right) {
let pivot = input[left + Math.floor((right - left) / 2)],
leftNew = left,
rightNew = right;
do {
while (input[leftNew] < pivot) {
leftNew++;
}
while (pivot < input[rightNew]) {
rightNew--;
}
if (leftNew <= rightNew) {
let temp = input[leftNew];
input[leftNew] = input[rightNew];
input[rightNew] = temp;
leftNew++;
rightNew--;
}
yield display(input, {pos: pivot, highlight:new Set([leftNew, pivot, rightNew])});
} while (leftNew <= rightNew);
yield* quicksort(left, rightNew);
yield* quicksort(leftNew, right);
}
}
yield* quicksort(0, input.length - 1);
yield display(input, {done: true});
}
heapSort = {
let input = makeInput();
yield* pauser(display(input, { immediate: true }));
function swap(data, i, j) {
var tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
function* heapSort(arr) {
yield* putArrayInHeapOrder(arr);
for (let end = arr.length - 1; end > 0; end--) {
yield display(input, {pos: end, highlight:new Set([end])});
swap(arr, 0, end);
yield* siftElementDownHeap(arr, 0, end);
}
}
function* putArrayInHeapOrder(arr) {
for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
yield* siftElementDownHeap(arr, i, arr.length);
}
}
function* siftElementDownHeap(heap, i, max) {
while (i < max) {
let i_big = i;
let c1 = 2 * i + 1;
let c2 = c1 + 1;
if (c1 < max && heap[c1] > heap[i_big])
i_big = c1;
if (c2 < max && heap[c2] > heap[i_big])
i_big = c2;
if (i_big == i) return;
yield display(input, {pos: i, highlight:new Set([i])});
swap(heap, i, i_big);
i = i_big;
}
}
yield* heapSort(input);
yield display(input, {done: true});
}
import {pauser} from "@tmcw/pauser"
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.
