Array.sort と Array.sortOn は不安定なソート

June 10, 2008category: Flash 

ActionScript 3.0 の Array.sort と Array.sortOn は不安定なソートなので、オブジェクトのキーでソートする際には注意が必要。

price というメンバを持つオブジェクトを 100 個作って、price をキーにソートする例。まずは Array.sort。 

var array:Array = [];
var object:Object;
for (var i:int = 0; i < 100; i++) {
  object = {};
  object.name = "Test" + (i.toString().length == 1 ? "0" + i : i);
  object.price = Math.random() * 100 | 0;
  array.push(object);
}

array.sort(function(a:Object, b:Object):int {
  var aPrice:Number = a.price;
  var bPrice:Number = b.price;
  if (aPrice > bPrice) {
    return 1;
  } else if (aPrice < bPrice) {
    return -1;
  } else {
    return 0;
  }
});

for each (var o:Object in array) {
  trace(o.name, o.price);
}

結果はこうなる。 

Test15 0
Test09 1
Test92 1
Test59 2
Test38 3
Test27 4
Test96 4
Test85 5
Test61 5
Test56 7
Test06 7
Test18 7
...

5 と 7 に不安定な並びがある。

次に Array.sortOn。 

array.sortOn("price", Array.NUMERIC);

結果。 

Test46 0
Test56 1
Test06 3
Test89 3
Test99 4
Test07 7
Test90 9
Test78 9
Test12 9
Test03 10
Test35 10
...

9 に不安定な並びがある。

ActionScript 1.0 の頃は、マージソートをポーティングした。そのコードだと比較関数を指定できないので、ActionScript 3.0 版を新しく書き直そうと思う。すでにライブラリがありそうな気もするが。

comments (0)このエントリーを含むはてなブックマークはてなブックマーク - Array.sort と Array.sortOn は不安定なソート

comments