Quicksort

Code

function quickSort(a) {

  let step = 0;
  let pivot = -1;

  if (a !== undefined && a !== null) {
    sort(a, 0, a.length - 1);
    printStep(++step, a, -1, -1, pivot);    
  }

  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(++step, 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);
    }
  }

  function printStep(s, a, i, j, p) {
    let k = undefined;
    let str = 'Step ' + s + ': '
    while (str.length < 9) str = ' ' + str;
    for (k = 0; k < a.length; k++) {
      if (k > 0) str += ',';
      if (k === i) str += '[';
      if (k === p) str += '|';
      str += a[k];
      if (k === j) str += ']';
      if (k === p) str += '|';
    }
    console.log(str);
  }

  function printSwap(a, i, j) {
    let k = undefined;
    let str = '  ' + i + '⇔' + j + ': ';
    while (str.length < 8) str = ' ' + str;
    for (k = 0; k < a.length; k++) {
      if (k > 0) str += ',';
      if (k === i || k === j) str += '[';
      str += a[k];
      if (k === i || k === j) str += ']';
    }
    console.log(str);
  }
}

let s = [503,087,512,061,908,170,897,275,653,426,154,509,612,677,765,703];
quickSort(s);

Steps

503,87,512,49,908,170,897,275,653,426,154,509,612,677,765,703
275,87,154,49,426,170,503,897,653,908,512,509,612,677,765,703
170,87,154,49,275,426,503,897,653,908,512,509,612,677,765,703
49,87,154,170,275,426,503,897,653,908,512,509,612,677,765,703
49,87,154,170,275,426,503,897,653,908,512,509,612,677,765,703
49,87,154,170,275,426,503,897,653,908,512,509,612,677,765,703
49,87,154,170,275,426,503,765,653,703,512,509,612,677,897,908
49,87,154,170,275,426,503,677,653,703,512,509,612,765,897,908
49,87,154,170,275,426,503,509,653,612,512,677,703,765,897,908
49,87,154,170,275,426,503,509,653,612,512,677,703,765,897,908
49,87,154,170,275,426,503,509,512,612,653,677,703,765,897,908
49,87,154,170,275,426,503,509,512,612,653,677,703,765,897,908

Steps and Swaps

  Step 1: [503,87,512,49,908,170,897,275,653,426,154,509,612,677,765,703]
   2⇔10: 503,87,[512],49,908,170,897,275,653,426,[154],509,612,677,765,703
    4⇔9: 503,87,154,49,[908],170,897,275,653,[426],512,509,612,677,765,703
    6⇔7: 503,87,154,49,426,170,[897],[275],653,908,512,509,612,677,765,703
    0⇔6: [503],87,154,49,426,170,[275],897,653,908,512,509,612,677,765,703
  Step 2: [275,87,154,49,426,170],|503|,897,653,908,512,509,612,677,765,703
    4⇔5: 275,87,154,49,[426],[170],503,897,653,908,512,509,612,677,765,703
    0⇔4: [275],87,154,49,[170],426,503,897,653,908,512,509,612,677,765,703
  Step 3: [170,87,154,49],|275|,426,503,897,653,908,512,509,612,677,765,703
    0⇔3: [170],87,154,[49],275,426,503,897,653,908,512,509,612,677,765,703
  Step 4: [49,87,154],|170|,275,426,503,897,653,908,512,509,612,677,765,703
  Step 5: |49|,[87,154],170,275,426,503,897,653,908,512,509,612,677,765,703
  Step 6: 49,|87|,154,170,275,426,503,[897,653,908,512,509,612,677,765,703]
   9⇔15: 49,87,154,170,275,426,503,897,653,[908],512,509,612,677,765,[703]
   7⇔14: 49,87,154,170,275,426,503,[897],653,703,512,509,612,677,[765],908
  Step 7: 49,87,154,170,275,426,503,[765,653,703,512,509,612,677],|897|,908
   7⇔13: 49,87,154,170,275,426,503,[765],653,703,512,509,612,[677],897,908
  Step 8: 49,87,154,170,275,426,503,[677,653,703,512,509,612],|765|,897,908
   9⇔12: 49,87,154,170,275,426,503,677,653,[703],512,509,[612],765,897,908
   7⇔11: 49,87,154,170,275,426,503,[677],653,612,512,[509],703,765,897,908
  Step 9: 49,87,154,170,275,426,503,[509,653,612,512],|677|,703,765,897,908
 Step 10: 49,87,154,170,275,426,503,|509|,[653,612,512],677,703,765,897,908
   8⇔10: 49,87,154,170,275,426,503,509,[653],612,[512],677,703,765,897,908
 Step 11: 49,87,154,170,275,426,503,509,[512,612],|653|,677,703,765,897,908
 Step 12: 49,87,154,170,275,426,503,509,|512|,612,653,677,703,765,897,908