9月 032017
 

これまでC#の安定ソートが欲しくて色々と検討していました。

アロケーションを気にしなければ、LinkedListについては各要素にインデックス振ったListを作ってSort()するのが速いという結果が出ていました。その実装をここにまとめます。List版もありますが、先の記事で検討したマージソートの方が速いので、Listではそっちを使ったほうがいいです。性能比較については前回の記事を参照。

Continue reading »

9月 032017
 

(2017/09/10 パフォーマンス比較にOrderByを追加。それに伴い、結論をやや修正)

ListとLinkedListの挿入ソートおよびマージソートを実装します。どちらも安定ソートです。

何を考えて実装したのか、長々と別の記事に書いてあるので、興味があればそっちもよろしくです。

マージソートを単純に実装するより、対象となる要素数が少ない時は挿入ソートのほうが速いので、挿入ソートに差し替える対応をします。なので、マージソートの実装がメインで、最適化の副産物で挿入ソートもあるよ、という感じです。

Continue reading »

9月 032017
 

Unityでゲームプログラムを書いていると、C#で気軽に使える安定ソートが欲しくなるのですが、これという機能が標準で用意されていません。

今更ソートなんて自前で実装したくないんですが、欲しいものがなければ作るしかない。実装までに検討した色々なことをこの記事ではまとめていきます。

実装したものは別の記事にまとめたので、そちらをどうぞ。

アルゴリズム系の実装コードって何故かほとんど可読性が低いですよね。主に変数名がやっつけすぎて理解に時間がかかります。バグの温床だと思うので、そのへんも私なりに読みやすくしています。

その点、これからいくらか紹介する.NETやMonoの実装はとても綺麗で理解しやすいです。

Continue reading »

Top