You are reading a single comment by @TiCPU and its replies. Click here to read the full conversation.
  • Attaching did not work, I'll just paste it inline:

    // Useful functions
    Array.prototype.median = function () {
      return this[Math.floor(this.length/2)];
    };
    Uint16Array.prototype.median = Array.prototype.median;
    
    Array.prototype.swap = function (left, right) {
      var tmp = this[left];
      
      this[left] = this[right];
      this[right] = tmp;
      
      return this;
    };
    Uint16Array.prototype.swap = Array.prototype.swap;
    
    Uint16Array.prototype.clear = function () {
      for (var i = 0; i < this.length; i++) this[i] = 0;
    };
    
    // Bubble sort
    Array.prototype.sort = function () {
      var len = this.length - 1;
    
      for (var i = 0; i < len; i++) {
        for (var j = 0, swapping, endIndex = len - i; j < endIndex; j++) {
          if (this[j] > this[j + 1]) {
            swapping = this[j];
            this[j] = this[j + 1];
            this[j + 1] = swapping;
          }
        }
      }
      return this;
    };
    Uint16Array.prototype.sort = Array.prototype.sort;
    
    // Quick sort
    Array.prototype.qsort_partition = function (pivot, left, right) {
      var tmp, storeIndex = left, pivotVal = this[pivot];
    
      this.swap(pivot, right);
      for (var i = left; i < right; i++) {
        if (this[i] < pivotVal) {
          this.swap(i, storeIndex);
          storeIndex++;
        }
      }
      this.swap(right, storeIndex);
    
      return storeIndex;
    };
    Uint16Array.prototype.qsort_partition = Array.prototype.qsort_partition;
    
    Array.prototype.qsort = function (left, right) {
      var pivot, newPivot;
    
      if (left === undefined) {
        left = 0;
        right = this.length - 1;
      }
    
      if (left < right) {
        pivot = left + Math.ceil((right - left) / 2);
        newPivot = this.qsort_partition(pivot, left, right);
        this.qsort(left, newPivot - 1);
        this.qsort(newPivot + 1, right);
      }
    
      return this;
    };
    Uint16Array.prototype.qsort = Array.prototype.qsort;
    
    // Tests
    var tQsort = new Uint16Array([5454,5449,5380,5412,5380,53­66,5344,5395,5398,5424,5422,5473,5420,54­32,5376,5354,5561,5288,5393,5388,5422,54­27,5476,5407,5385,5180,5363,5324,5395,53­93,5410,5405,5349,5361,5385,5412,5373,53­73,5478,5420,5446,5395,5339,5407,5420,53­56,5336,5427,5459,5378,5336,5349,5420,54­05,5434,5383,5446,5422,5349,5329,5405,54­34,5446,5336,5427,5473,5402,5170,5388,54­12,5456,123,456,789]);
    var tBsort = new Uint16Array([5454,5449,5380,5412,5380,53­66,5344,5395,5398,5424,5422,5473,5420,54­32,5376,5354,5561,5288,5393,5388,5422,54­27,5476,5407,5385,5180,5363,5324,5395,53­93,5410,5405,5349,5361,5385,5412,5373,53­73,5478,5420,5446,5395,5339,5407,5420,53­56,5336,5427,5459,5378,5336,5349,5420,54­05,5434,5383,5446,5422,5349,5329,5405,54­34,5446,5336,5427,5473,5402,5170,5388,54­12,5456,123,456,789]);
    
    var qsortTime, bsortTime, startTime = getTime();
    tQsort.qsort();
    qsortTime = getTime();
    tBsort.sort();
    bsortTime = getTime();
    
    print("start: " + startTime);
    print("qsort: " + qsortTime + " (" + (qsortTime-startTime) + ")");
    print("bsort: " + bsortTime + " (" + (bsortTime-qsortTime) + ")");
    
About

Avatar for TiCPU @TiCPU started