   
（１）ソート済み配列のマージ
ソート済み配列をマージして，
新しいソート済み配列を作ることができます。
この処理は単純であり，かつ時間計算量もＯ（Ｎ）となります。
（２）マージソートの考え方
マージの考え方を応用したソートを
マージソート（merge sort）と呼びます。
マージソートでは，分割してマージソートしたものを
マージします。すなわち再帰的な処理となります。
再帰的な呼び出しを含めたデータの流れは，次のようになります。
（３）マージソートのアルゴリズム
配列の要素数が2以上のとき，
@）配列の前半部をマージソートする。
A）配列の後半部をマージソートする。
B）配列の前半部と後半部をマージする。
の手順でソートします。
なお，マージの時間計算量はＯ（N），
マージソートの階層は，log Nですから
マージソートの時間計算量は，Ｏ（N log N）となります。
［プログラム］
private void MergeSort(ref int[] a, int
左, int 右)
{
if(左 <右)
{
int 中央 =(左 + 右)/2;
MergeSort(ref a, 左, 中央);
MergeSort(ref a, 中央 + 1, 右);
int[] temp= new int[右 - 左 +
1];
int p=0; int i; int j=0;
int
k=左;
for(i=左; i <= 中央; i++)
temp[p++]=a[i];
while(i <= 右 && j<p)
a[k++]=(temp[j]<=a[i]) ? temp[j++]:a[i++];
while(j < p) a[k++]
= temp[j++];
}
}
private void マージソート()
{
MergeSort(ref Data,0, Data.Length-1);
}
 1. 基本的なアルゴリズム
2. 基本的なデータ構造
3. 操作を伴うデータ構造
4. 探索
5. 再帰的アルゴリズム
6. ソート
7. 集合
8. 文字列処理
9. 色々なアルゴリズム
上のタイトルをクリックします
|
6．7 マージソート