Skip to content

Instantly share code, notes, and snippets.

@philer
Last active January 26, 2016 16:03
Show Gist options
  • Save philer/a9c5b0df087e2a9f8572 to your computer and use it in GitHub Desktop.
Save philer/a9c5b0df087e2a9f8572 to your computer and use it in GitHub Desktop.
Visualization of simple sorting algorithms in GeoGebra using JavaScript with a few custom utility functions.
/**
* This file is part of a GeoGebra project for
* visualizing sorting algorithms.
*
* Last update 2014-12-11
* Runs on GeoGebra 4.2.60.0 Linux 32bit
*
* @author Philipp Miller
*/
/* bootstrap */
function ggbOnInit() {
set("lenght", 30);
setArray("input", randomArray(get("length")));
clearSnapshots();
}
/*** SORTING ALGORITHMS ***/
/* Sorts array in place using simple bubble sort */
function bubbleSort(arr) {
var snapshots = [arr.slice(0)];
for (var i = 0, len = arr.length ; i < len ; ++i) {
for (var k = 0 ; k < len-1 ; ++k) {
if (arr[k] > arr[k+1]) {
swap(arr, k, k+1);
snapshots.push(arr.slice(0));
}
}
}
setSnapshots(snapshots);
}
/* Sorts array in place using simple insertion sort */
function insertionSort(arr) {
var snapshots = [arr.slice(0)];
for (var i = 1, len = arr.length ; i < len ; ++i) {
for (var k = i-1 ; k >= 0 && arr[k] > arr[k+1]; --k) {
swap(arr, k, k+1);
snapshots.push(arr.slice(0));
}
}
setSnapshots(snapshots);
}
/* Sorts array in place using simple merge sort */
function mergeSort(arr) {
var snapshots = [];
mergeSortRecursive(arr, 0, arr.length - 1, snapshots);
setSnapshots(snapshots);
}
function mergeSortRecursive(arr, first, last, snapshots) {
if (last <= first) return;
var middle = Math.floor((first + last) / 2);
mergeSortRecursive(arr, first, middle, snapshots);
mergeSortRecursive(arr, middle+1, last, snapshots);
var l = first,
r = middle + 1,
tmpArr = [];
while (l <= middle && r <= last) {
tmpArr.push(arr[l] < arr[r] ? arr[l++] : arr[r++]);
}
while (l <= middle) tmpArr.push(arr[l++]);
while (r <= last) tmpArr.push(arr[r++]);
for (var n = first ; n <= last ; ++n) {
arr[n] = tmpArr[n - first];
snapshots.push(arr.slice(0));
}
return arr;
}
/* Sorts array in place using simple quick sort */
function quickSort(arr) {
var snapshots = [];
quickSortRecursive(arr, 0, arr.length - 1, snapshots);
setSnapshots(snapshots);
}
function quickSortRecursive(arr, first, last, snapshots) {
if (last <= first) return;
var pivot = Math.floor((first + last) / 2);
var pivotVal = arr[pivot];
swap(arr, pivot, last);
snapshots.push(arr.slice(0));
var k = first;
for (var i = first ; i < last ; ++i) {
if (arr[i] < pivotVal) {
swap(arr, i, k);
snapshots.push(arr.slice(0));
++k;
}
}
swap(arr, k, last);
snapshots.push(arr.slice(0));
quickSortRecursive(arr, first, k-1, snapshots);
quickSortRecursive(arr, k+1, last, snapshots);
}
/*** SNAPSHOTS (ANIMATION) ***/
function clearSnapshots() {
setMatrix("steps", [getArray("input")]); /* do this first */
setSlider("step", {max: 0, value: 0}); /* DO NOT DELET "step" */
}
function setSnapshots(arr) {
setMatrix("steps", arr);
var len = arr.length - 1;
setSlider("step", {min: 0, max: len, speed: 2, value: 0});
}
function showSnapshot() {
drawArray(getMatrixRow("steps", get("step")));
}
/* SLOW! */
function snapshot(arr, i) {
appendMatrix("steps", arr);
setSlider("step", {max: i});
}
/*** JS LIBRARY */
function randomArray(len, min, max) {
if (max === undefined) {
max = min;
min = 0;
}
if (max === undefined) max = len;
var arr = [], i = len;
while(i--) arr[i] = Math.floor(Math.random()*(max-min) + min);
return arr;
}
function shuffledRange(len) {
var arr = [], j;
for (var i = 0 ; i < len ; ++i) {
j = Math.floor(Math.random() * i);
arr[i] = arr[j];
arr[j] = i;
}
return arr;
}
function strToInt(x) {
return +x;
}
function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/*** GEOGEBRA API ***/
function get(name) {
return ggbApplet.getValue(name);
}
function set(name, value) {
ggbApplet.evalCommand(name + "=" + value);
}
function del() {
Array.prototype.slice.call(arguments).forEach(function(name) {
if (ggbApplet.exists(name)) {
ggbApplet.deleteObject(name);
}
});
}
function getArray(name) {
return ggbApplet
.getValueString(name)
.replace(' ','')
.match(/\{(.*)\}/)[1]
.split(",")
.map(function (x) {
return +x;
});
}
function setArray(name, arr) {
set(name, "{" + arr + "}");
}
function drawArray(arr, name) {
name = name || "bars";
if (typeof arr === "string") {
arr = getArray(arr);
}
del(name);
set(name, "BarChart[0," + arr.length + ",{" + arr + "}]");
}
function getMatrix(name) {
return ggbApplet
.getValueString(name)
.replace(' ','')
.match(/\{\{(.*)\}\}/)[1]
.split("\},\{")
.map(function (xs) {
return xs.split(",").map(strToInt);
});
}
function getMatrixRow(name, row) {
var str = ggbApplet.getValueString(name).replace(' ',''),
len = str.length(),
i = 0,
k;
for (row += 2; row && i < len ; ++i) {
if (str.charAt(i) === 123) --row;
}
if (row) return [];
for (k = i ; k < len && str.charAt(k) !== 125 ; k++);
return str
.slice(i,k)
.split(",")
.map(strToInt);
}
function setMatrix(name, arrs) {
set(name, "{{" + arrs.join("},{") + "}}");
}
function appendMatrix(name, arr) {
ggbApplet.evalCommand(
ggbApplet.getValueString(name).slice(0,-2) + "},{" + arr + "}}"
);
}
function setSlider(name, data) {
set(name, "Slider["
+ (data.min || 0) + "," /*Min*/
+ data.max + "," /*Max*/
+ (data.step || 1) + "," /*Increment*/
+ (data.speed || 3) + "," /*Speed*/
+ (data.width || 100) + "," /*Width*/
+ "False," /*Is Angle*/
+ "True," /*Horizontal*/
+ "True," /*Animating*/
+ "False" /*Random*/
+ "]");
if (data.value !== undefined) {
set(name, data.value);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment