javascriptnode.jssortingshellsort

How to write shell sort on Node.js


I'm trying to write a shellsort on Node.js like on the book Algorithms, 4th ed. Sedgewick, Wayne. There all the examples written on Java.

Here is my module:

"use strict";

module.exports = (function() {

  function sort(array) {
    let size = array.length;
    let h = 1;
    while(h < size/3) {
      h = h * 3 + 1;
    }
    while(h >= 1) {
      for(let i = h; i < size; i++) {
        for(let j = i; j >= h && less(array, j, j-h); j = j-h) {
          exch(array, j, j-h);
        }
      }
      h = h/3;
    }
  }

  function less(array, i, min) {
    return array[i] < array[min];
  }

  function exch(array, i, min) {
    let temp = array[i];
    array[i] = array[min];
    array[min] = temp;
  }

  return {
    sort: sort
  };

})();

I use mocha and chai for testing with this function:

function isSorted(array) {
  for(let i = 1, size = array.length; i < size; i++) {
    if (array[i] < array[i-1]) {
      return false;
    }
  }
  return true;
}

and shell sort not working: mocha test screenshot


Solution

  • Your h may become a floating point number if you use h = h / 3. Try h = Math.floor(h / 3); instead.