今回はシアソート (またはシェアソート) です。このアルゴリズムはリストを2次元テーブルに見立てて、行と列ごとに繰り返しソートすることで最終的にはリスト全体がソートされるというアルゴリズムです。各行、各列をソートするときのアルゴリズムは任意です。
このアルゴリズムのメリットは列ごとにソートを行うときに各行または各列ごとに独立して並列にソートすることができるので適切に実装を行えばマルチプロセッサ環境で高速にソートできることです。
下記はJavaによる実装です。
2010年2月25日 | カテゴリー：アルゴリズム
今回はトポロジカルソートというアルゴリズムを説明します。
トポロジカルソートは有効グラフの位相順序を求めるアルゴリズムです。といっても誰も分かってくれないと思うので分かりやすく説明しますと、ある非循環有向グラフがあるとして、全ての辺(u, v) に対して
頂点 u の番号 < 頂点 v の番号
となるように接点の番号をつけるアルゴリズムです。
非循環有向グラフであるの必要があるのは、循環していると上の不等式が成り立たなくなるためです。
Javaによるサンプルコードを示します。
2010年2月10日 | カテゴリー：アルゴリズム
バケットソートを紹介します。
このソートは要素の値の範囲が決まっている配を高速に並び替えるのに役立ちます。汎用のソートアルゴリズム(要素の値の範囲が決まっていないソート)では多くの場合、計算量はO(nlogn)であるのに対し、このソートではO(n)で計算できます。
ただし、要素の値が取り得る値の範囲の数だけの格納領域が必要です。例えば、要素に対する仮定が 「int 型の整数である」というだけであるとするとその取り得る値の範囲は0～4294967296の約43億個分の整数を格納する領域が必要になります。
以下はバケットソートの特に分布数えソートと呼ばれるアルゴリズムのJavaのサンプルです。
2010年1月26日 | カテゴリー：アルゴリズム
