7
\$\begingroup\$

I'm trying to implement a bunch of sorting algorithms in JavaScript, and I can't figure out why my shell sort is so slow. It's 6x slower than my merge sort, and only slightly faster than my insertion sort. I've seen another implementation online, but I'm more focused on making it clear and readable (as I have a blog for noobs) and the faster implementation is too concise for my purposes. Any thoughts on how I can keep the general plan but get it moving faster? I tried using Marcin Ciura's gap sequence [701, 301, 132, 57, 23, 10, 4, 1], but it was slightly slower. I'm not sure what's the biggest factor slowing down my sort.

  var shellSort = function( list ) {
    var gapSize = Math.floor( list.length / 2 );

    while( gapSize > 0 ) {
      _shellInsertionSort( list, gapSize );
      gapSize = Math.floor( gapSize / 2 );
    }

    return list;
  };

  function _shellInsertionSort( list, gapSize ) {
    var temp, i, j;

    for( i = gapSize; i < list.length; i += gapSize ) {
      j = i;
      while( j > 0 && list[ j - gapSize ] > list[j] ) {
        temp = list[j];
        list[j] = list[ j - gapSize ];
        list[ j - gapSize ] = temp;
        j -= gapSize;
      }
    }
  };

My tests:

  var testSpeed = function( testSize, rounds ) {
    var testArrays = [],
        algorithms = Array.prototype.slice.call( arguments, 2 ),
        results = [],
        i, j;

    for( i = 0; i < rounds; i++ ) {
      testArrays[i] = [];
      for( j = 0; j < testSize; j++ ) {
        testArrays[i].push( Math.ceil( Math.random() * testSize ));
      }
    }

    for( i = 0; i < algorithms.length; i++ ) {
      for( j = 0; j < rounds; j++ ) {
        if( !results[i] ) {
          results[i] = [];
        }
        results[i].push( testAlgorithm( algorithms[i], testArrays[j] ));
      }
    }

    return results;
  };

  var testAlgorithm = function( algorithm, set ) {
    var clone = set.slice(),
        start = new Date().getTime(),
        end;

    algorithm( clone );

    end = new Date().getTime();

    return end - start;
  };
\$\endgroup\$
2
  • 2
    \$\begingroup\$ The while test should be j >= gapSize to keep from checking negative indices with j - gapSize, but that should barely make a dent in the speed. \$\endgroup\$ Mar 1, 2014 at 1:23
  • 2
    \$\begingroup\$ And the psuedocode on the Wikipedia page increments i by 1 rather than gapSize in the outer for loop. While that means more iterations, perhaps it people forms better by sorting more large gaps. \$\endgroup\$ Mar 1, 2014 at 1:28

1 Answer 1

3
\$\begingroup\$

@David Harkness sent my search in the right direction. As it is, the insertion sort portion is only going through one round for each gap, rather than walking up each round, so it's not actually going for more than one round, and most of the sorting isn't done until the gap is 1. When I start fixing problem, it just started getting more convoluted, so I ditched my original approach and followed the pseudocode on wikidepia. Now, it's quite snappy:

var shellSort = function( list ) {
    var gap = Math.floor( list.length / 2 );

    while( gap > 0 ) {
      for( i = gap; i < list.length; i++ ) {
        temp = list[i];
        for( j = i; j >= gap && list[j - gap] > temp; j -= gap ) {
          list[j] = list[j - gap];
        }
        list[j] = temp;
      }

      gap = Math.floor( gap / 2 );
    }

    return list;
  };
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.