Dan☆Oniエディター で使っているソート

メモ程度にまとめ。

sort1

◆方法1  全部のコマを配置した後、Actionscriptデフォルトのsort()を使ってソート。
問題点:数が多くなるとソートに時間がかかる。

◆方法2  全部のコマを配置した後、クイックソートを使ってソート。
問題点:数が多くなるとソートに時間がかかる。

そもそも譜面製作は初めから順番に作っていくことが多いので、
ソート処理しなくてもある程度は順番通りになっている。
初めからランダムだと決めつけて全体ソートするのが問題。

◆方法3  1つのコマを追加するごとに挿入ソート。
sort2

この方法だと全体ソートしなくていいので、最後にソートする必要がなくなる。
実際1コマ分のソートならそれほどかからないし、出力時間も大きく減った。

しかし譜面製作上、追加するコマはたいてい要素の最後付近になることが多い。
最初から見ていったのでは、結局最後まで要素比較しているのと同じになってしまう。
このため、現在は方法4の方法でソートしている。

◆方法4  1つのコマを追加するごとに二分探索。
sort3

◆次のための自分用メモ
32分配置などの理由により、そのままソートするとコマ順序が逆転することがある。
見た目はほとんどが整列済み(ソート済み)のため、
整列されていないところを切り出してマージソートを使うのが良さそう。

コメントを残す

メールアドレスは公開されません

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください