comparefn follow-up

.js

色々とおかしかったので前回の記事を訂正した。
テスト用の配列を「Math.random()」で作成したのが明らかな間違い(0 を返すべきペアがほぼ生じないのだから「-.5 or .5」でソートできるのは当然)で「Math.random() > .1」に変更して要素数を増やしたところ SpiderMonkey/Rhino/JScript でのみ有効という残念な結果になった。

蛇足

なぜダメなのかを探る。幸い Google Chrome は sort の中身が丸見えである。

javascript:'<pre>'+[].sort

function sort(comparefn) {
  var custom_compare = (typeof(comparefn) === 'function');
  function Compare(x,y) {
    if (custom_compare) {
      return comparefn.call(null, x, y);
    }
    if (_IsSmi(x) && _IsSmi(y)) {
      return SmiLexicographicCompare(x, y);
    }
    x = ToString(x);
    y = ToString(y);
    if (x == y) return 0;
    else return x < y ? -1 : 1;
  };
  function InsertionSort(a, from, to) {
    for (var i = from + 1; i < to; i++) {
      var element = a[i];
      var min = from;
      var max = i;
      while (min < max) {
        var mid = min + ((max - min) >> 1);
        var order = Compare(a[mid], element);
        if (order == 0) {
          min = max = mid;
          break;
        }
        if (order < 0) {
          min = mid + 1;
        } else {
          max = mid;
        }
      }
      for (var j = i; j > min; j--) {
        a[j] = a[j - 1];
      }
      a[min] = element;
    }
  }
  function QuickSort(a, from, to) {
    if (to - from <= 22) {
      InsertionSort(a, from, to);
      return;
    }
    var pivot_index = $floor($random() * (to - from)) + from;
    var pivot = a[pivot_index];
    a[pivot_index] = a[to - 1];
    a[to - 1] = pivot;
    var low_end = from;
    var high_start = to - 1;
    for (var i = from; i < high_start; ) {
      var element = a[i];
      var order = Compare(element, pivot);
      if (order < 0) {
        a[i] = a[low_end];
        a[low_end] = element;
        low_end++;
        i++;
      } else if (order > 0) {
        high_start--;
        a[i] = a[high_start];
        a[high_start] = element;
      } else {
        i++;
      }
    }
    a[to - 1] = a[high_start];
    a[high_start] = pivot;
    high_start++;
    QuickSort(a, from, low_end);
    QuickSort(a, high_start, to);
  }
  var old_length = ToUint32(this.length);
  RemoveArrayHoles(this);
  var length = ToUint32(this.length);
  for (var i = 0; i < length; ) {
    if ((typeof(this[i]) === 'undefined')) {
      length--;
      this[i] = this[length];
      this[length] = void 0;
    } else {
      i++;
    }
  }
  QuickSort(this, 0, length);
  if (HasArrayClass(this)) {
    this.length = old_length;
  }
  return this;
}
  • QuickSort は Compare の値で三分割し，-1 と 1 の部分に対してのみ再帰。長さが 22 以下になると InsertionSort に切り替え。

クイックソートの教科書的実装。同値の部分が多ければ再帰を重ねずに済むが，分割が偏ると苦しい。

[1, 0, -1].map(function(x){
  var count = 0, a = [], i = 100;
  while(i--) a[i] = 1;
  a.sort(function(){ ++count; return x });
  return x + ': '+ count;
}).join(' / ')

1: 499348 / 0: 999 / -1: 499331