function quickSort(a) {
let pivot = -1;
sort(a, 0, a.length - 1);
printStep(a, -1, -1, pivot);
// utilities
function output(s) {
console.log(s);
}
function padWithZeros(n, len) {
let s = n.toString();
let count = len - s.length;
while (count-- > 0) {
s = '0' + s;
}
return s;
}
function printStep(a, i, j, p) {
let k = undefined;
let str = '';
for (k = 0; k < a.length; k++) {
if (k > 0) str += ',';
if (k === i) str += '[';
if (k === p) str += '|';
str += padWithZeros(a[k], 3);
if (k === j) str += ']';
if (k === p) str += '|';
}
output(str);
}
function printSwap(a, i, j) {
let k = undefined;
let str = '';
for (k = 0; k < a.length; k++) {
if (k > 0) str += ',';
if (k === i || k === j) str += '(';
str += padWithZeros(a[k], 3);
if (k === i || k === j) str += ')';
}
output(str);
}
function partition(a, n, i, j) {
while (a[i] < n && i < j) {
i++;
}
while (a[j] >= n && j > i) {
j--;
}
if (i < j) {
printSwap(a, i, j);
let tmp = a[i];
a[i] = a[j];
a[j] = tmp;
if (i + 1 === j) {
return i;
}
else {
return partition(a, n, i + 1, j - 1);
}
}
else { // i and j are equal
return a[i] < n ? i : i - 1;
}
}
function sort(a, first, last) {
printStep(a, first, last, pivot);
let n = a[first];
let i = first + 1;
let j = last;
let k = partition(a, n, i, j);
pivot = k;
if (k > first) {
printSwap(a, first, k);
a[first] = a[k];
a[k] = n;
}
if (k - 1 > first) {
sort(a, first, k - 1);
}
if (k + 1 < last) {
sort(a, k + 1, last);
}
}
}
// Leading zeros implies octal if all digits are in 0-7; 061: 6*8 + 1 = 49.
let s = [503,87,512,61,908,170,897,275,653,426,154,509,612,677,765,703];
quickSort(s);