Zen andThe Art of Computer Programming: Quicksort JavaScript Program

503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703
275,087,154,061,426,170,503,897,653,908,512,509,612,677,765,703
170,087,154,061,275,426,503,897,653,908,512,509,612,677,765,703
061,087,154,170,275,426,503,897,653,908,512,509,612,677,765,703
061,087,154,170,275,426,503,897,653,908,512,509,612,677,765,703
061,087,154,170,275,426,503,897,653,908,512,509,612,677,765,703
061,087,154,170,275,426,503,765,653,703,512,509,612,677,897,908
061,087,154,170,275,426,503,677,653,703,512,509,612,765,897,908
061,087,154,170,275,426,503,509,653,612,512,677,703,765,897,908
061,087,154,170,275,426,503,509,653,612,512,677,703,765,897,908
061,087,154,170,275,426,503,509,512,612,653,677,703,765,897,908
061,087,154,170,275,426,503,509,512,612,653,677,703,765,897,908

[503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703]
503,087,(512),061,908,170,897,275,653,426,(154),509,612,677,765,703
503,087,154,061,(908),170,897,275,653,(426),512,509,612,677,765,703
503,087,154,061,426,170,(897),(275),653,908,512,509,612,677,765,703
(503),087,154,061,426,170,(275),897,653,908,512,509,612,677,765,703
[275,087,154,061,426,170],|503|,897,653,908,512,509,612,677,765,703
275,087,154,061,(426),(170),503,897,653,908,512,509,612,677,765,703
(275),087,154,061,(170),426,503,897,653,908,512,509,612,677,765,703
[170,087,154,061],|275|,426,503,897,653,908,512,509,612,677,765,703
(170),087,154,(061),275,426,503,897,653,908,512,509,612,677,765,703
[061,087,154],|170|,275,426,503,897,653,908,512,509,612,677,765,703
|061|,[087,154],170,275,426,503,897,653,908,512,509,612,677,765,703
061,|087|,154,170,275,426,503,[897,653,908,512,509,612,677,765,703]
061,087,154,170,275,426,503,897,653,(908),512,509,612,677,765,(703)
061,087,154,170,275,426,503,(897),653,703,512,509,612,677,(765),908
061,087,154,170,275,426,503,[765,653,703,512,509,612,677],|897|,908
061,087,154,170,275,426,503,(765),653,703,512,509,612,(677),897,908
061,087,154,170,275,426,503,[677,653,703,512,509,612],|765|,897,908
061,087,154,170,275,426,503,677,653,(703),512,509,(612),765,897,908
061,087,154,170,275,426,503,(677),653,612,512,(509),703,765,897,908
061,087,154,170,275,426,503,[509,653,612,512],|677|,703,765,897,908
061,087,154,170,275,426,503,|509|,[653,612,512],677,703,765,897,908
061,087,154,170,275,426,503,509,(653),612,(512),677,703,765,897,908
061,087,154,170,275,426,503,509,[512,612],|653|,677,703,765,897,908
061,087,154,170,275,426,503,509,|512|,612,653,677,703,765,897,908

<style scoped="">
pre {
  display: inline-block;
}
pre:hover .next {
  background-color: yellow;
}
pre:hover .pivot {
  background-color: yellow;
  font-weight: bold;
}
pre:hover .pivoted {
  background-color: mediumseagreen;
  color: white;
}
pre:hover .swap {
  background-color: lightblue;
}
pre:hover .todo {
  background-color: gold;
}
pre:hover .done {
  background-color: tomato;
  color: white;
}
.hidden {
  display: none;
}
</style>

<script>
(function() { // don't trash the namespace

  function main() {

    function hide(element) {
      element.classList.add('hidden');
    }

    function show(element) {
      element.classList.remove('hidden');
    }

    function hideAll() {
      hide(collapsedTable);
      hide(expandedTable);
      hide(sortCode);
      hide(postCode);
    }

    function selectionChanged() {
      hideAll();
      switch(selector.selectedIndex) {
      case 0:
        show(collapsedTable);
        break;
      case 1:
        show(expandedTable);
        break;
      case 2:
        show(sortCode);
        break;
      case 3:
        show(postCode);
        break;
      }
    }

    function removeInjectedTags(html) {
      function removeTag(str, tag, attr) {
        const pattern = '<' + tag + attr + '><\/' + tag + '>';
        const regExp = new RegExp(pattern, 'gi');
        return str.replace(regExp, '');
      }
      html = removeTag(html, 'script', '\ src=".*"');
      return removeTag(html, 'div', '\ style=".*"');
    }

    function initialize() {
      let html = postCode.parentElement.innerHTML;
      hideAll();
      show(collapsedTable);
      selector.addEventListener('change', selectionChanged);
      postCode.textContent = removeInjectedTags(html);
      selectionChanged();
    }

    const selector = document.getElementById('what-to-display');
    const expandedTable = document.getElementById('expanded-table');
    const collapsedTable = document.getElementById('collapsed-table');
    const sortCode = document.getElementById('sort-code');
    const postCode = document.getElementById('post-code');
    initialize();
  }

  document.addEventListener('DOMContentLoaded', main);

})();
</script>

<p>
<select id="what-to-display">
  <option>Summary</option>
  <option selected="">Output</option>
  <option>Program</option>
</select>
</p>

<pre id="collapsed-table"><span class="pivot" title="next pivot">503</span><span class="next" title="set to partition">,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703</span>
<span class="pivot" title="next pivot">275</span><span class="next" title="left partition">,087,154,061,426,170</span>,<span class="pivoted" title="pivot (sorted)">503</span>,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
<span class="pivot" title="next pivot">170</span><span class="next" title="left partition">,087,154,061</span>,<span class="pivoted" title="pivot (sorted)">275</span>,<span class="done" title="right partition (sorted)">426</span>,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
<span class="pivot" title="next pivot">061</span><span class="next" title="left partition">,087,154</span>,<span class="pivoted" title="pivot (sorted)">170</span>,275,426,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
<span class="pivoted" title="pivot (sorted)">061</span>,<span class="pivot" title="next pivot">087</span><span class="next" title="right partition">,154</span>,170,275,426,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
061,<span class="pivoted" title="pivot (sorted)">087</span>,<span class="done" title="right partition (sorted)">154</span>,170,275,426,503,<span class="pivot" title="next pivot">897</span><span class="next" title="set to partition">,653,908,512,509,612,677,765,703</span>
061,087,154,170,275,426,503,<span class="pivot" title="next pivot">765</span><span class="next" title="left partition">,653,703,512,509,612,677</span>,<span class="pivoted" title="pivot (sorted)">897</span>,<span class="done" title="right partition (sorted)">908</span>
061,087,154,170,275,426,503,<span class="pivot" title="next pivot">677</span><span class="next" title="left partition">,653,703,512,509,612</span>,<span class="pivoted" title="pivot (sorted)">765</span>,897,908
061,087,154,170,275,426,503,<span class="pivot" title="next pivot">509</span><span class="next" title="left partition">,653,612,512</span>,<span class="pivoted" title="pivot (sorted)">677</span>,<span class="done" title="right partition (sorted)">703</span>,765,897,908
061,087,154,170,275,426,503,<span class="pivoted" title="pivot (sorted)">509</span>,<span class="pivot" title="next pivot">653</span><span class="next" title="right partition">,612,512</span>,677,703,765,897,908
061,087,154,170,275,426,503,509,<span class="pivot" title="next pivot">512,</span><span class="next" title="left partition">612</span>,<span class="pivoted" title="pivot (sorted)">653</span>,677,703,765,897,908
061,087,154,170,275,426,503,509,<span class="pivoted" title="pivot (sorted)">512</span>,<span class="done" title="right partition (sorted)">612</span>,653,677,703,765,897,908
</pre>

<pre id="expanded-table" class="hidden">[<span class="pivot" title="next pivot">503</span><span class="next" title="set to partition">,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703</span>]
503,087,(<span class="swap">512</span>),061,908,170,897,275,653,426,(<span class="swap">154</span>),509,612,677,765,703
503,087,154,061,(<span class="swap">908</span>),170,897,275,653,(<span class="swap">426</span>),512,509,612,677,765,703
503,087,154,061,426,170,(<span class="swap">897</span>),(<span class="swap">275</span>),653,908,512,509,612,677,765,703
(<span class="swap">503</span>),087,154,061,426,170,(<span class="swap">275</span>),897,653,908,512,509,612,677,765,703
[<span class="pivot" title="next pivot">275</span><span class="next" title="left partition">,087,154,061,426,170</span>],|<span class="pivoted">503</span>|,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
275,087,154,061,(<span class="swap">426</span>),(<span class="swap">170</span>),503,897,653,908,512,509,612,677,765,703
(<span class="swap">275</span>),087,154,061,(<span class="swap">170</span>),426,503,897,653,908,512,509,612,677,765,703
[<span class="pivot" title="next pivot">170</span><span class="next" title="left partition">,087,154,061</span>],|<span class="pivoted">275</span>|,<span class="done">426</span>,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
(<span class="swap">170</span>),087,154,(<span class="swap">061</span>),275,426,503,897,653,908,512,509,612,677,765,703
[<span class="pivot" title="next pivot">061</span><span class="next" title="left partition">,087,154</span>],|<span class="pivoted">170</span>|,275,426,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
|<span class="pivoted">061</span>|,[<span class="pivot" title="next pivot">087</span><span class="next" title="right partition">,154</span>],170,275,426,503,<span class="todo" title="right partition (on hold)">897,653,908,512,509,612,677,765,703</span>
061,|<span class="pivoted">087</span>|,<span class="done">154</span>,170,275,426,503,[<span class="pivot" title="next pivot">897</span><span class="next" title="set to partition">,653,908,512,509,612,677,765,703</span>]
061,087,154,170,275,426,503,897,653,(<span class="swap">908</span>),512,509,612,677,765,(<span class="swap">703</span>)
061,087,154,170,275,426,503,(<span class="swap">897</span>),653,703,512,509,612,677,(<span class="swap">765</span>),908
061,087,154,170,275,426,503,[<span class="pivot" title="next pivot">765</span><span class="next" title="left partition">,653,703,512,509,612,677</span>],|<span class="pivoted">897</span>|,<span class="done">908</span>
061,087,154,170,275,426,503,(<span class="swap">765</span>),653,703,512,509,612,(<span class="swap">677</span>),897,908
061,087,154,170,275,426,503,[<span class="pivot" title="next pivot">677</span><span class="next" title="left partition">,653,703,512,509,612</span>],|<span class="pivoted">765</span>|,897,908
061,087,154,170,275,426,503,677,653,(<span class="swap">703</span>),512,509,(<span class="swap">612</span>),765,897,908
061,087,154,170,275,426,503,(<span class="swap">677</span>),653,612,512,(<span class="swap">509</span>),703,765,897,908
061,087,154,170,275,426,503,[<span class="pivot" title="next pivot">509</span><span class="next" title="left partition">,653,612,512</span>],|<span class="pivoted">677</span>|,<span class="done">703</span>,765,897,908
061,087,154,170,275,426,503,|<span class="pivoted">509</span>|,[<span class="pivot" title="next pivot">653</span><span class="next" title="right partition">,612,512</span>],677,703,765,897,908
061,087,154,170,275,426,503,509,(<span class="swap">653</span>),612,(<span class="swap">512</span>),677,703,765,897,908
061,087,154,170,275,426,503,509,[<span class="pivot" title="next pivot">512,</span><span class="next" title="left partition">612</span>],|<span class="pivoted">653</span>|,677,703,765,897,908
061,087,154,170,275,426,503,509,|<span class="pivoted">512</span>|,<span class="done">612</span>,653,677,703,765,897,908
</pre>

<pre id="post-code" class="hidden"></pre>

<pre id="sort-code" class="hidden">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-- &gt; 0) {
      s = '0' + s;
    }
    return s;
  }

  function printStep(a, i, j, p) {
    let k = undefined;
    let str = '';
    for (k = 0; k &lt; a.length; k++) {
      if (k &gt; 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 &lt; a.length; k++) {
      if (k &gt; 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] &lt; n &amp;&amp; i &lt; j) {
      i++;
    }
    while (a[j] &gt;= n &amp;&amp; j &gt; i) {
      j--;
    }
    if (i &lt; 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] &lt; 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 &gt; first) {
      printSwap(a, first, k);
      a[first] = a[k];
      a[k] = n;
    }
    if (k - 1 &gt; first) {
      sort(a, first, k - 1);
    }
    if (k + 1 &lt; 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);
</pre>

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);

Zen and
The Art of Computer Programming

Pages

Quicksort JavaScript Program