Skip to content

Instantly share code, notes, and snippets.

@tamask
Created July 13, 2011 14:51
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tamask/1080446 to your computer and use it in GitHub Desktop.
Save tamask/1080446 to your computer and use it in GitHub Desktop.
In-place, non-recursive qsort in Javascript
function qsort(a, k, l, r) {
// a: array to sort, k: key to sort by,
// l, r: optional array index array range
// i: stack index, s: stack,
// p: pivot index, v: pivot value,
// t: temporary array item,
// x, y: partion low/high
var i, s, p, v, t, x, y;
l = l || 0;
r = r || a.length - 1;
i = 2;
s = [l, r];
while (i > 0) {
r = s[--i];
l = s[--i];
if (l < r) {
// partition
x = l;
y = r - 1;
p = l;
v = a[p];
a[p] = a[r];
while (true) {
while (
x <= y &&
a[x] != undefined &&
a[x][k] < v[k])
x++;
while (
x <= y &&
a[y] != undefined &&
a[y][k] >= v[k])
y--;
if (x > y)
break;
t = a[x];
a[x] = a[y];
a[y] = t;
}
a[r] = a[x];
a[x] = v;
// end
s[i++] = l;
s[i++] = x - 1;
s[i++] = x + 1;
s[i++] = r;
}
}
}
@Alyksett
Copy link

variable names like these are unproductive

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment