代表的な 6種類の並べ替えアルゴリズムについて簡単に説明し、Java のアプレットによって実際に並べ替えがはたらく様子を示しました。また、6種類のアルゴリズムを比較して、バブルソートは O(N²)、その他のソートは O(N log(N)) で並べ替えが実行できていると言うことも確認しました。

実際にデータを並べ替えてみると、速度的に優れているのは、やはりクイックソートです。このアルゴリズムは、C 言語では qsort() という標準関数として提供されていますが、残念ながら Java には標準ではついていません。しかし、自分で作るのもそれほど難しいアルゴリズムではないですから、是非、自分でトライしてみてください。

また、アルゴリズムを実際にコーディングする場合、その実装方法によって処理効率は大きく変わる場合があることも覚えておいてください。今回は、バケットソートや基数ソートを実装する際に双方向リンクリスト DListInt を使用しました。これは整数専用の双方向リンクリストですが、リンクの腕を使うために DLinkInt というラッパークラスを使用しています。このため、リストへの追加の際に必ず new 演算を行うので、その文のオーバーヘッドが生じます。さらに、細かい new の繰り返しはメモリのフラグメントを進行させ、ガベージコレクションの発生頻度が大きくなると考えられます。これは、速度の低下に直結します。

Java では、あらゆるオブジェクトがヒープに確保されるので大変便利ですが、反面、メモリの使用法についてよく理解して使わないと、思わぬ速度低下を招いたりする危険があります。

-- TOP --