fc2ブログ



マージソート Merge Sort

2007.02.18 01:06  整列

マージソートは、高速でかつ安定なソートアルゴリズムです。しかも、効率はやや劣りますが、クイックソートと比べると実装が簡単で理解もし易いアルゴリズムです。高速で安定という特徴から、様々なところで実用されています。

マージソートのアルゴリズムは分割統治法を応用します。そして、マージソートは分割統治法を説明するための最も良い例ともなるので、分割統治法のアイデアもついでに知ることができます。下図は、マージソートの流れを表しています。

mergeSort.gif


ステップ1配列による入力データ
ステップ2 配列を2つに分割する
ステップ3 分割された部分配列をさらに分割する
ステップ4 分割された部分配列をさらに分割する
ステップ5 部分配列の要素数が 1 でこれ以上分割することができないので、2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ6 分割された部分配列をさらに分割する
ステップ7 2 つの部分配列を統治する。統治するときに要素を昇順にソートする
ステップ8 2 つの部分配列を統治する。統治するときに要素を昇順にソートする.
ポイント:これら 2 つの部分配列の要素はすでにソート済みである
ステップ9-14 同様に、ステップ 2 で分割された部分配列を分割-統治する
ステップ15 2 つの部分配列を統治する。統治するときに要素を昇順にソートする.
ポイント:これら 2 つの部分配列の要素はすでにソート済みである.
配列のソートが完了する


マージソートの流れの論理的な構造は、ツリー(木)となっていますが、実装するためにツリーのデータ構造を用いる必要はありません。しかし、データを配列で処理する場合、マージソートはその倍のメモリ空間を必要とすることが、マージソートの欠点でもあります。実装は以下のように非常にシンプルな構成となります。


マージソートのプログラムは、mergeSort と merge の2つの部分から構成されています。まず、配列全体を指定した mergeSort を呼び出します。mergeSort は与えられた配列を前半後半の2つに分割します。その2つについてそれぞれさらに mergeSort を行います(再帰により実現する)。mergeSort は配列の要素数が 1 以下のときは何もせずに終了します。そして、各 mergeSort の最後で、分割された前後2つの配列を merge します。merge を実行する時点で、mergeSort( 部分配列の前半 ) と mergeSort( 部分配列の後半 ) がすでに終了しているので、merge はすでにソートされている部分配列の前半と後半に対して実行されます。言い換えれば、merge の役割は、すでにソートされている2つの部分配列を1つのソートされた部分配列にすることです。

プログラム例:部分配列の先頭のインデックスを left、部分配列の(末尾 + 1)のインデックスを right とした場合





この merge 関数は番兵を使ってやや巧妙な処理をしています。以下の図は、この merge のメカニズムをカードの操作で表したものです。左右にカードの束があり、各束のカードは小さい順に整列されているものとします。そして、カードの最下部に番兵としてジョーカーを追加配置します。

マージの処理は、各カードの山のてっぺんの値を比べ、小さい方を選択して順番に並べていきます。この操作の過程で、あるカードとジョーカーを比べる局面が発生しますが、ジョーカーが選ばれることはありません。つまり、番兵にはどのカード(数字)と比べても負けることのない大きな数を割り当てるのです。

ジョーカーすなわち番兵の設置によって、マージの際にカードの束が空になったか否かのチェックをする必要がなくなります。なぜなら、カードを選択する回数を、ジョーカーを除いたカードの合計値とすれば、ジョーカーが比べられることも、カードの束が空になることもないからです。束が空になったか否かのチェックは、プログラム上では配列の範囲を超えるか否かのチェックとなるので、番兵の設置は処理の高速化にも繋がり(微々たるものですが、)プログラムが読みやすくなります。

mergeSortMerge.gif


次に示す、merge のプログラムは、さらに巧妙なテクニックを用いています。プログラムの動作を考えてみましょう。



マージソートの計算効率は、データがどのような特徴を持っていても O(nlogn) となります。上図に示したマージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるからです。

実戦でマージソートを自分で最初から実装することはまずないと思われますが、分割統治法、再起、番兵のアイデア、などを学べる良いアルゴリズムの1つではないでしょうか。
スポンサーサイト



| コメント(2) | トラックバック(0) | ↑ページトップ |




バブルソート Bubble Sort

2006.05.19 22:11  整列

選択ソートはある決められた範囲から、最小値を見つけ要素の交換を行いました。バブルソートは、隣り合う要素の比較のみを繰り返すことによって並び替えを行います。

バブルソートのアルゴリズムを以下に示します。

バブルソート
各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。 未ソートの部分がなくなるまで、以下の処理を繰り返します。
  1. データの先頭から隣どうしを比較して、大小関係が逆ならばそれらを交換していきます。この交換処理を未ソートの部分の末尾まで順番に行います。

バブルソートはその名前からイメージできるように、泡(Bubble)が水面に上がっていくようにデータが動いていきます。上記のアルゴリズムでは、ソートされたデータが配列の後ろから順番に決定されていきます。

具体的な例で、バブルソートの流れを初期状態から見てみましょう。上図に示す処理が終了すると、データの中で一番大きい要素が配列の末尾に移動します。続きの処理を下図に示します。

バブルソート

上図のステップ1.~5.が終了すると、データの中で2番目に大きい要素が配列の後ろから2番目に移動します。以下同様に、ステップ6.~9.、ステップ10.~12.、ステップ13.~14.でそれぞれソート済みの部分に追加されるデータが決まっていきます。

以下のプログラムはは、データの数 size を読み込み、size個の整数のデータを配列 data に読み込んで、配列の要素をバブルソートによって昇順に整列し、それを出力します。プログラムの本体である bubbleSort を見てみましょう。下図に示すように、07行目の最初のループ変数であるendは未ソートの部分の末尾を示します。08行目のforループによってデータの先頭からendまでの範囲で、隣どうしを比較して逆順ならば交換する処理を繰り返します。この2番目のループが終わると、その範囲のなかで一番大きい値がソートされていない部分の末尾に移動します。
バブルソート



バブルソートの計算量を考えてみましょう。データの数をnとすると、バブルソートは未ソートの部分における隣どうしの比較演算をn-1回、n-2回、n-3回、・・・、1回行います。よって合計の比較演算の回数は(n2-n)/2となり、バブルソートはO(n2)のアルゴリズムとなります。

練習問題

| コメント(0) | トラックバック(0) | ↑ページトップ |




選択ソート セレクションソート Selection Sort

2006.04.20 00:13  整列

選択ソートは、ソートアルゴリズムの導入となる最も単純なアルゴリズムの1つです。最も思いつきやすく、直感的なアルゴリズムだと思います。

選択ソート
各計算ステップにおいて、配列は「ソート済みの部分」と「未ソートの部分」とに分けられます。
selectionSortStep2.gif
1.「未ソートの部分」から最小の要素を探します。
選択ソート
2. 選ばれた最小の要素と未ソートの部分の先頭の要素を交換します。
選択ソート
1. 2. を未ソートの部分がなくなるまで繰り返します。

選択ソート
1. 初期状態は全ての要素が未ソートの部分に属します。
2. 未ソートの部分から最小値2を選択し、未ソートの部分の先頭7と交換します。
3. 未ソートの部分から最小値3を選択し、未ソートの部分の先頭5と交換します。
4. 未ソートの部分から最小値5を選択し、未ソートの部分の先頭11と交換します。
5. 未ソートの部分から最小値6を選択し、未ソートの部分の先頭8と交換します。
6. 未ソートの部分から最小値7を選択し、未ソートの部分の先頭12と交換します。
7. 未ソートの部分から最小値8を選択し、未ソートの部分の先頭11と交換します。
8. 未ソートの部分から最小値11を選択し、未ソートの部分の先頭12と交換します。
9. ソートが完了します。


選択ソートインデックス

Program は、データの数 size を読み込み、size個の整数を配列 data に読み込んで、配列の要素を選択ソートによって昇順に整列し、それを出力します。プログラムの本体である selectionSort を見てみましょう。07行目の最初の for ループによって、「未ソートの部分の最小値と先頭の要素を交換する処理」を繰り返します。Fig.に示すように、front は未ソートの部分の先頭の要素を指します。次の10行目のforループによって、未ソートの部分から最小値を見つけます。インデックスminIndexが最小値を示すように、minIndexを更新していきます。14-16で、最小値と先頭の要素を交換します。

選択ソートの計算量を考えてみましょう。データの数をnとすると、選択ソートは未ソートの部分の最小値を見つけるためにn-1回、n-2回、n-3回・・・1回の比較演算を行います。よって合計の比較演算の回数は(n2-n)/2となり、選択ソートはO(n2)のアルゴリズムとなります。

| コメント(0) | トラックバック(0) | ↑ページトップ |




ソートのアルゴリズム

2006.04.20 00:08  整列

様々なソートアルゴリズムが考案されてきましたが、用途やデータの特徴、またはプログラムで使うデータ構造などに応じて、それらを的確に選ばなくてはなりません。以下の表は、代表的なソートのアルゴリズムとそれらの効率・特徴を示しています。

アルゴリズムの名前 効率 安定性 特徴
選択ソート
(Selection Sort)
O(n2) × 単純で最も直感的だが、効率が悪い
バブルソート
(Bubble Sort)
O(n2) 単純だが効率が悪い
挿入ソート
(Insertion Sort)
O(n2) ぼぼ整列されているデータに対して効率的
マージソート
(Merge Sort)
O(nlonn) 外部の記憶領域が必要
ヒープソート
(Heap Sort)
O(nlonn) × ヒープのデータ構造を応用する
クイックソート
(Quick Sort)
O(nlonn) × ほぼ整列されているデータに対して効率的ではない


選択ソート、バブルソートはソートのアルゴリズムの導入に紹介されるくらいで、実践で(現場で)使うことはほんとんどありません。データの特徴や問題の仕様に合わせて適切なアルゴリズムを設計することが重要です。マージソートは安定で高速、しかも実装が比較的容易なのでおすすめです。クイックソートは、理論上最速と言われていますが、安定ではないので注意が必要です。

| コメント(0) | トラックバック(0) | ↑ページトップ |




安定なソート

2006.04.20 00:06  整列

アルゴリズムを設計、選ぶ際に重要なポイントとなるのがその効率ですが、整列のアルゴリズムに関しては、それが「安定なソート」であるかを考慮に入れなくてはなりません。安定なソートとは、キーの値が同じ要素が2つ以上あるデータセットにおいては、それらの要素をソート前とソート後で順番が変わらないようなソート方法です。以下の例を見てみましょう。


stableSort.gif


上の例は、同じデータを整列したもので、どちらの配列もデータが昇順に並べ替えられましたが、左が「安定なソート」、右が「安定でないソート」です。このデータには、2つの「3」があります。「緑の3」と「青の3」です。初期データは、「緑の3」→「青の3」の順番となっていますが、「安定なソート」ではこの順番が保たれています。一方、「安定でないソート」では、「青の3」→「緑の3」と順番が逆になっています。

このソートの安定性を考慮に入れなければ、思わぬ失敗をしてしまいます。




stableSortCards.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |




整列 ソート

2006.04.20 00:05  整列

整列されたデータは探索(検索)し易い、ということをすでに紹介しました。データの整列は、多くのアルゴリズムの基礎になります。たくさんのデータを、あるキーに従って昇順(小さい順)または降順(大きい順)に整列するためのアルゴリズムをいくつか記録したいと思います。

sort.gif

| コメント(0) | トラックバック(0) | ↑ページトップ |