The other day I wrote an article about JavaScript binary trees and mentioned that the native JavaScript sort was probably faster than using a binary tree for sorting. I decided to write a few sort algorithms in JavaScript and see how they compared to the native ".sort()".

I tested each sort method with three types of data sets. The first data set was made up of all the same number, the second set was an ascending series of numbers, and the third set was made up of random numbers between zero and four hundred. I used different data set sizes, from 25 to 4000. Finally, I ran the test 22 times, discarded the highest and lowest results, and averaged the remaining results.
As you may have guessed, the native JavaScript sort method handily beat all of the methods that I implemented. There really were no surprises, but it gave me the opportunity to implement various sort algorithms. It is hard to make it out in the picture above, but the built-in sort function is displayed on the graph as a nearly vertical white line. The black line above it is quicksort. This graph show the performance of these algorithms on the random data set.

My empirical analysis also showed that the red-headed-stepchild of algorithms, bubble sort, could actually beat the king, quicksort, under carefully constructed conditions. The graph below shows the results when sorting attempting to sort an array that is already sorted. The furthest left black line shows the terrible performance of quicksort under these conditions. Bubble sort performed well, it was only beat by its big brother cocktail sort and sort() which again beat all of my implementations.
The moral of the story is that you don't want to use quick sort on arrays that are already nearly sorted. Furthermore, the built-in JavaScript ".sort()" can beat all of my implementations using any of my data sets for nearly every data set size.

For the curious my code is listed below:


<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<head>
  <title>Sort Tester</title>
  <meta http-equiv="Content-Type" 
    content="application/xhtml+xml; charset=iso-8859-1" />
  <meta name="generator" 
    content="Christopher Stoll - using a text editor" />
  <link rel="start" href="/" />
  <link rel="icon" 
    type="image/vnd.microsoft.icon" 
    href="img/favicon.ico" />
  <link rel="shortcut icon" 
    type="image/vnd.microsoft.icon" 
    href="img/favicon.ico" />
  <link rel="stylesheet" 
    type="text/css" 
    href="css/main.css" />
  <script type="text/javascript" 
    src="js/jquery-1.4.2.min.js"></script>
  <script type="text/javascript" 
    src="js/Array.extrasort.js"></script>
  <script type="text/javascript">
    /**
     * sortTest object constructor
     *
     * @constructor
     * @this {sortTest}
     */
     function sortTest(){
      // array to be sorted
      this._array = [];
      // array of sort times (length is _num_times)
      this._times = [];
      // number of times to sort the array
      this._numTests = 12;
      
      // the array modes
      this.modes = {random:0, same:1, ascending:2};
      // the sort types
      this.sorts = {
        default:  {id:0, name:'sort()'},
        bubble:    {id:1, name:'bubble'},
        cocktail:  {id:2, name:'cocktail'},
        heap:    {id:3, name:'heap'},
        insertion:  {id:4, name:'insertion'},
        merge:    {id:5, name:'merge'},
        quick:    {id:6, name:'quick'},
        radix:    {id:7, name:'radix'},
        selection:  {id:8, name:'selection'},
        tree:    {id:9, name:'tree'}
      }
      
      // array of array sizes to test
      this.arraySizes = 
        [25, 50, 75, 100, 200, 400, 600, 800, 1000
        1200, 1400, 1600, 2000, 2200, 2400, 2600, 2800
        3200, 3400, 3600, 3800, 4000];
      // 400 random nums from 000-400 
      // (the random number generator wasn't working well)
      this._array400 = 
        [191, 137, 335, 070, 382, 399, 287, 107, 016, 302
        310, 324, 363, 113, 019, 198, 305, 238, 390, 366,
        199, 201, 503, 161, 012, 266, 281, 325, 314, 213,
        335, 197, 284, 362, 395, 068, 359, 143, 233, 356,
        025, 144, 308, 352, 280, 029, 328, 313, 284, 064,
        074, 128, 202, 392, 001, 351, 200, 392, 261, 230,
        073, 218, 022, 133, 376, 030, 082, 253, 134, 146,
        065, 171, 299, 251, 255, 269, 105, 274, 302, 185,
        321, 345, 057, 280, 244, 074, 081, 165, 126, 098,
        140, 277, 255, 000, 004, 072, 132, 170, 165, 281,
        026, 132, 200, 184, 338, 297, 348, 231, 356, 337,
        114, 219, 070, 185, 041, 090, 193, 012, 010, 243,
        144, 013, 236, 238, 140, 054, 105, 094, 292, 021,
        124, 332, 123, 019, 129, 138, 368, 303, 391, 090,
        002, 270, 232, 274, 382, 067, 386, 371, 009, 183,
        239, 218, 086, 097, 037, 239, 388, 030, 360, 174,
        146, 267, 260, 152, 133, 209, 168, 320, 234, 055,
        130, 374, 396, 049, 346, 034, 277, 093, 360, 163,
        253, 051, 216, 259, 384, 110, 355, 208, 206, 383,
        158, 163, 296, 304, 196, 098, 115, 123, 122, 073,
        239, 218, 086, 097, 037, 239, 388, 030, 360, 174,
        146, 267, 260, 152, 133, 209, 168, 320, 234, 055,
        130, 374, 396, 049, 346, 034, 277, 093, 360, 163,
        253, 051, 216, 259, 384, 110, 355, 208, 206, 383,
        158, 163, 296, 304, 196, 098, 115, 123, 122, 073,
        010, 334, 293, 067, 354, 323, 314, 269, 292, 399,
        175, 281, 156, 309, 132, 031, 161, 075, 363, 103,
        262, 133, 322, 098, 305, 323, 386, 369, 198, 023,
        166, 233, 266, 140, 038, 389, 342, 110, 291, 037,
        328, 263, 147, 060, 255, 231, 096, 392, 197, 028,
        199, 071, 187, 270, 268, 325, 366, 278, 017, 204,
        289, 180, 242, 377, 133, 112, 388, 260, 166, 136,
        163, 037, 373, 178, 074, 220, 304, 163, 206, 118,
        028, 099, 281, 377, 202, 286, 214, 239, 209, 128,
        229, 239, 141, 340, 309, 094, 298, 028, 299, 347,
        027, 296, 041, 059, 112, 281, 188, 002, 037, 400,
        118, 033, 338, 399, 367, 050, 302, 048, 097, 258,
        297, 057, 055, 316, 159, 133, 268, 010, 245, 031,
        215, 235, 009, 242, 113, 112, 268, 037, 182, 074,
        104, 326, 180, 159, 375, 264, 229, 288, 312, 273,
        340, 204, 057, 306, 073, 221, 173, 283, 279, 394];
    }
      /**
       * fill array with values
       *
       * @private
       * @this {sortTest}
       * @param {numeric} pnum size of the array
       * @param {boolean} pmod the mode
       */
      sortTest.prototype._fillArray = function(pnum, pmod) {
        var tmod = pmod || this.modes.random,
          count0=0;
          
        this._array = [];
        
        // array with ascending numbers
        if(tmod == this.modes.ascending){
          for(var i=0; i<pnum; i++){
            this._array[i] = i;
          }
        // array with same number
        } else if(tmod == this.modes.same){
          for(var i=0; i<pnum; i++){
            this._array[i] = 123;
          }
        // array with random numbers
        } else {
          if(pnum <= 400){
            for(var i=0; i<pnum; i++){
              this._array[i] = this._array400[i];
            }
          } else {
            for(var i=0; i<pnum; i++){
              if(i>400){
                count0 = 
                  Math.floor(Math.random()*400);
                this._array[i] = 
                  this._array400[count0];
              } else {
                this._array[i] = 
                  this._array400[i];
              }
            }
          }
        }
      }
      
      /**
       * fill with random values that are nearly sorted
       *
       * @this {sortTest}
       * @param {numeric} pnum size of the array
       */
      sortTest.prototype.gen = function(pnum) {
        this._fillArray(pnum); 
      }

      /**
       * fill array with ascending values
       *
       * @this {sortTest}
       * @param {numeric} pnum size of the array
       */
      sortTest.prototype.genAscending = function(pnum) {
        this._fillArray(pnum, this.modes.ascending);
      }
      
      /**
       * fill array same values
       *
       * @this {sortTest}
       * @param {numeric} pnum size of the array
       */
      sortTest.prototype.genSame = function(pnum) {
        this._fillArray(pnum, this.modes.same);
      }
      
      /**
       * get the average time from the times array
       *
       * @private
       * @this {sortTest}
       * @return {numeric} the average time
       */
      sortTest.prototype._timeAvg = function(){
        var time_sum = 0// sum of the times
          time_min = 0// the minimum time
          time_max = 0// the maximum time
          time_avg = 0// the average time
        
        // use the first item as the default minimum
        time_min = this._times[0];
        
        for(var i=0; i<this._numTests; i++){
          time_sum += this._times[i];
          
          // so we can discard highest and lowest
          if(this._times[i] < time_min){
            time_min = this._times[i];
          } else if(this._times[i] > time_max){
            time_max = this._times[i];
          }
        }
        // average time is the sum minus the high
        // and low divided by nuber minus two
        time_avg = 
          (time_sum - time_min - time_max) / 
          (this._numTests - 2);
        return time_avg.toFixed(2);
      }
      
      /**
       * get a timestamp
       *
       * @private
       * @this {sortTest}
       * @return {numeric} time stamp
       */
      sortTest.prototype._getTS = function() {
        var datetime = new Date();
        return datetime.getTime();
      }
      
      /**
       * run the specified sort
       *
       * @this {sortTest}
       * @param {numeric} ptype The type of sort
       * @return {numeric} Changed succesfully
       */
      sortTest.prototype.run = function(ptype){
        var ttype = ptype || this.sorts.default,
          time_beg = 0// the starting time
          time_end = 0// the ending time
          time_tot = 0// end time minus start time
          tmp_array = [];  // array to sort
          
        for(var i=0; i<this._numTests; i++){
          // get a fresh COPY (use slice) of array
          tmp_array = this._array.slice(0);
          
          switch(ttype){
            // this sorts as strings
            case this.sorts.default:
              time_beg = this._getTS();
              tmp_array.sort();
              time_end = this._getTS();
              break;
            case this.sorts.bubble:
              time_beg = this._getTS();
              tmp_array.bubbleSort();
              time_end = this._getTS();
              break;
            case this.sorts.cocktail:
              time_beg = this._getTS();
              tmp_array.cocktailSort();
              time_end = this._getTS();
              break;
            case this.sorts.selection:
              time_beg = this._getTS();
              tmp_array.selectionSort();
              time_end = this._getTS();
              break;
            case this.sorts.insertion:
              time_beg = this._getTS();
              tmp_array.insertionSort();
              time_end = this._getTS();
              break;
            case this.sorts.merge:
              time_beg = this._getTS();
              tmp_array = tmp_array.mergeSort();
              time_end = this._getTS();
              break;
            case this.sorts.heap:
              time_beg = this._getTS();
              tmp_array = tmp_array.heapSort();
              time_end = this._getTS();
              break;
            case this.sorts.quick:
              time_beg = this._getTS();
              tmp_array = tmp_array.quickSort();
              time_end = this._getTS();
              break;
            case this.sorts.radix:
            //  time_beg = this._getTS();
            //  tmp_array.radixSort();
            //  time_end = this._getTS();
              break;
            case this.sorts.tree:
            //  time_beg = this._getTS();
            //  tmp_array.treeSort();
            //  time_end = this._getTS();
              break;
          }
          
          // total time, stored
          time_tot = time_end - time_beg;
          this._times[i] = time_tot;
        }
        
        this._array = [];
        this._array = tmp_array;
        return this._timeAvg();
      }
      
    /*
     * ***** ***** ***** ***** *****
     * Above is the tester program
     * Below is the GUI portion
     * ***** ***** ***** ***** *****
     */
     
    $(document).ready(function() {
      var resultHead = '<tr><th>method</th>';
        resultHead += '<th>n</th>';
        resultHead += '<th>same number</th>';
        resultHead += '<th>ascending numbers</th>';
        resultHead += '<th>random numbers</th></tr>';
      $('#results').append(resultHead);
      
      sorter = new sortTest();
    });
      
    function runSort(pSortType) {
      var result_same = 0,
        result_ascending = 0,
        result_random = 0,
        result = '',
        skip = false;
      
      // run for each array size
      for(var i=0; i<sorter.arraySizes.length; i++){
        skip = false;
        
        if(sorter.arraySizes[i]>1000 && 
        pSortType == sorter.sorts.quick)
          {skip = true;}
        if(sorter.arraySizes[i]>2000 && 
        pSortType == sorter.sorts.selection)
          {skip = true;}
        
        // run for a uniform array (if it is not too big)
        if(!skip){
          sorter.genSame(sorter.arraySizes[i]);
          result_same = sorter.run(pSortType);
        } else {
          result_same = 999;
        }
        
        // run for a sorted array (if it is not too big)
        if(!skip){
          sorter.genAscending(sorter.arraySizes[i]);
          result_ascending = sorter.run(pSortType);
        } else {
          result_ascending = 999;
        }
        
        if(pSortType == sorter.sorts.quick)
          {skip = false;}
        if(sorter.arraySizes[i]>1200 && 
        pSortType == sorter.sorts.bubble)
          {skip = true;}
        if(sorter.arraySizes[i]>1400 && 
        pSortType == sorter.sorts.cocktail)
          {skip = true;}
        if(sorter.arraySizes[i]>2000 && 
        pSortType == sorter.sorts.insertion)
          {skip = true;}
        
        // run for a random(ish) array (if not too big)
        if(!skip){
          sorter.gen(sorter.arraySizes[i]);
          result_random = sorter.run(pSortType);
        } else {
          result_random = 999;
        }
        
        result =  '<td>' + pSortType.name + '</td>';
        result += '<td>' + sorter.arraySizes[i] + '</td>';
        result += '<td>' + result_same + '</td>';
        result += '<td>' + result_ascending + '</td>';
        result += '<td>' + result_random + '</td>';
        $('#results').append('<tr>'+result+'</tr>');
      }
    }
  </script>
</head><body>
  <div id="app_data"></div>
  <div id="colc">
    <div class="head" id="controls">
      <input type="button" value="Run deafult" 
        onclick="runSort(sorter.sorts.default);">
      <input type="button" value="Run bubble" 
        onclick="runSort(sorter.sorts.bubble);">
      <input type="button" value="Run cocktail" 
        onclick="runSort(sorter.sorts.cocktail);">
      <input type="button" value="Run selection" 
        onclick="runSort(sorter.sorts.selection);">
      <input type="button" value="Run insertion" 
        onclick="runSort(sorter.sorts.insertion);">
      <input type="button" value="Run merge" 
        onclick="runSort(sorter.sorts.merge);">
      <input type="button" value="Run heap" 
        onclick="runSort(sorter.sorts.heap);">
      <input type="button" value="Run quick" 
        onclick="runSort(sorter.sorts.quick);">
      <input type="button" value="Run radix" 
        onclick="runSort(sorter.sorts.radix);">
      <input type="button" value="Run tree" 
        onclick="runSort(sorter.sorts.tree);">
    </div>
    <table id="results"></table>
  </div>
</body>

Tags: Blogger JavaScript Code Algorithms

Published: 2010-04-10