メモ程度にまとめ。
◆方法1 全部のコマを配置した後、Actionscriptデフォルトのsort()を使ってソート。
問題点：数が多くなるとソートに時間がかかる。
◆方法2 全部のコマを配置した後、クイックソートを使ってソート。
問題点：数が多くなるとソートに時間がかかる。
そもそも譜面製作は初めから順番に作っていくことが多いので、
ソート処理しなくてもある程度は順番通りになっている。
初めからランダムだと決めつけて全体ソートするのが問題。
◆方法3 1つのコマを追加するごとに挿入ソート。
この方法だと全体ソートしなくていいので、最後にソートする必要がなくなる。
実際1コマ分のソートならそれほどかからないし、出力時間も大きく減った。
しかし譜面製作上、追加するコマはたいてい要素の最後付近になることが多い。
最初から見ていったのでは、結局最後まで要素比較しているのと同じになってしまう。
このため、現在は方法4の方法でソートしている。
◆方法4 1つのコマを追加するごとに二分探索。
◆次のための自分用メモ
32分配置などの理由により、そのままソートするとコマ順序が逆転することがある。
見た目はほとんどが整列済み(ソート済み)のため、
整列されていないところを切り出してマージソートを使うのが良さそう。
最近のコメント