argius note

プログラミング関連

ソートを勉強中

アルゴリズムを基礎からやり直そうと思い立って、アルゴリズム事典などを参考にソートアルゴリズムをいくつか書いてみた。バブルソート、選択ソート、挿入ソート、クイックソートを試す。テストはJUnitを使い、いくつかの配列での結果がArrays.sortの結果と同じならOKというテストを作ってからアルゴリズム実装。UnitTestはイイね。気に入った。
自作版ソートとArrays.sort(以下「標準」と記述)を比較。但し、int配列のみ。データは、randomで生成した配列のコピー(同じ内容の配列)を作成して比較。サイズは、10,000と50,000,000の2通り。JDKは1.4.2。
クイックソートvs標準は、五分五分な感じですが、クイックソートの要素数が少ないときに挿入ソートに切り替える「改良クイックソート」と比較すると、かなり差が出た。今回は大雑把な計測なので、次はもうちょっと整理してやってみよう。