<script type="text/javascript">
  //<![CDATA[

  //------------------------------------------------------------------------------
  // shared functions
  //------------------------------------------------------------------------------

  // initialize canvas
  function initializeCanvas(id) {
      var canvas = document.getElementById(id);
      if (canvas.getContext) {
          var ctx = canvas.getContext('2d');
          var width = Math.floor(window.innerWidth / 6) - 5;
          var height = Math.floor(width * 9 / 16);
          ctx.canvas.width = width;
          ctx.canvas.height = height;
          ctx.strokeStyle = '#AAAAAA';
          return ctx;
      }
  }

  // draw canvas
  function drawCanvas(ctx, arr) {
      var width = ctx.canvas.width;
      var height = ctx.canvas.height;
      var lineWidth = width / arr.length;
      ctx.clearRect(0, 0, width, height);
      for (var i = 0; i < arr.length; i++) {
          var lineHeight = Math.floor(height * arr[i] / arr.length);
          var x = Math.floor(i * lineWidth);
          ctx.beginPath();
          ctx.moveTo(x, height);
          ctx.lineTo(x, height - lineHeight);
          ctx.stroke();
      }
  }

  // shuffle
  function shuffle(arr) {
      for (var i = 0; i < arr.length; i++) {
          var j = Math.floor(Math.random() * (i + 1));
          var x = arr[j];
          arr[j] = arr[i];
          arr[i] = x;
      }
      return arr;
  }

  // current delay
  this.delay = 100;

  // set delay
  function setDelay(delay) {
      this.delay = delay;
  }

  // array size
  this.arraySize = 100;

  //------------------------------------------------------------------------------
  // selection sort
  //------------------------------------------------------------------------------

  // selection sort (one step at a time)
  var SelectionSort = function(ctx, arr) {
      this.ctx = ctx;
      this.arr = arr;
      this.i = 0;
      this.done = false;

      // perform next step and return arr
      this.next = function() {
          if (!this.done) {
              var min = this.i;
              for (var j = this.i; j < this.arr.length; j++) {
                  if (this.arr[j] < this.arr[min]) min = j;
              }
              var x = this.arr[min];
              this.arr[min] = this.arr[this.i];
              this.arr[this.i] = x;
              this.i = this.i + 1;
              if (this.i >= this.arr.length) this.done = true;
          }
          return this.arr;
      }
  }

  this.selectionSort;

  // iterate through selection sort
  function selectionSortLoop() {
      selectionSort.next();
      drawCanvas(selectionSort.ctx, selectionSort.arr);
      if (!selectionSort.done) setTimeout('selectionSortLoop()', this.delay);
  }

  // start selection sort
  function selectionSortStart() {
      // generate array
      var size = arraySize;
      var arr = [];
      for (var i = 0; i < size; i++) {
          arr[i] = i;
      }
      // shuffle array
      arr = shuffle(arr);
      // initialize canvas
      var ctx = initializeCanvas('canvasSelectionSort');
      if (ctx != undefined) {
          selectionSort = new SelectionSort(ctx, arr);
          drawCanvas(ctx, arr);
          setTimeout('selectionSortLoop()', this.delay);
      }
  }

  //------------------------------------------------------------------------------
  // insertion sort
  //------------------------------------------------------------------------------

  // insertion sort (one step at a time)
  var InsertionSort = function(ctx, arr) {
      this.ctx = ctx;
      this.arr = arr;
      this.i = 0;
      this.done = false;

      // perform next step and return arr
      this.next = function() {
          if (!this.done) {
              for (var j = this.i - 1; !(j < 0 || this.arr[j] <= this.arr[j + 1]); j--) {
                  var x = this.arr[j];
                  this.arr[j] = this.arr[j + 1];
                  this.arr[j + 1] = x;
              }
              this.i = this.i + 1;
              if (this.i >= this.arr.length) this.done = true;
          }
          return this.arr;
      }
  }

  this.insertionSort;

  // iterate through insertion sort
  function insertionSortLoop() {
      insertionSort.next();
      drawCanvas(insertionSort.ctx, insertionSort.arr);
      if (!insertionSort.done) setTimeout('insertionSortLoop()', this.delay);
  }

  // start insertion sort
  function insertionSortStart() {
      // generate array
      var size = arraySize;
      var arr = [];
      for (var i = 0; i < size; i++) {
          arr[i] = i;
      }
      // shuffle array
      arr = shuffle(arr);
      // initialize canvas
      var ctx = initializeCanvas('canvasInsertionSort');
      if (ctx != undefined) {
          insertionSort = new InsertionSort(ctx, arr);
          drawCanvas(ctx, arr);
          setTimeout('insertionSortLoop()', this.delay);
      }
  }

  //------------------------------------------------------------------------------

  // reset
  function start() {
      setTimeout('selectionSortStart()', 100);
      setTimeout('insertionSortStart()', 100);
  }

  window.onload = start;

  //]]>
</script>

<h1>Sorting Functions</h1>

&nbsp;&nbsp;
<a id="restart" href="javascript:start()">restart</a>
&nbsp;&nbsp;
<a id="slowSpeed" href="javascript:setDelay(1000)">slow</a>
&nbsp;&nbsp;
<a id="normalSpeed" href="javascript:setDelay(100)">normal</a>
&nbsp;&nbsp;
<a id="fastSpeed" href="javascript:setDelay(0)">fast</a>

<div>
  <div style="float:left">
    <h3>Selection Sort</h3>
    <canvas id="canvasSelectionSort" width="200" height="200">
      <p>Canvas is not supported on this browser.</p>
    </canvas>
  </div>
  <div style="float:left">
    &nbsp;&nbsp;
  </div>
  <div style="float:left">
    <h3>Insertion Sort</h3>
    <canvas id="canvasInsertionSort" width="200" height="200">
      <p>Canvas is not supported on this browser.</p>
    </canvas>
  </div>
</div>

<div style="clear:both">
</div>