Explain Sort Algorithms  

高速アルゴリズム

 ここでは高速に処理ができるアルゴリズムを紹介する。ここで高速と呼んでいるものは、O(nlogn)に分類できるものである。  

マージソート ( Mergesort )

 マージソートの基本的な考え方は、あらかじめ並べ替えが完了している2つのデータを1つに合併する操作を組織的に適用することによって、最終的にソートされたデータを得るものである。本来は、磁気テープによる外部ソートを行なう有力な方法として発達してきたが、ここでは内部ソートとして考えてみよう。以下簡単のため、データの個数を2のべき乗と仮定する。基本原理(マージ操作)を例によって示す。2本のソート済みの磁気テープが存在しているとする。

	 13   43   45   56 <----- テープ1
	  7   18   68   95 <----- テープ2
 
これらを、マージしよう。

			   13   43   45   56
	          	<
			    7   18   68   95

			   13   43   45   56
  7          	        <
			   18   68   95

			   43   45   56
  7  13          	<
		           18   68   95

			   43   45   56
  7  13  18      	<
		           68   95

		           45   56
  7  13  18  43  	<
		           68   95

			   56
  7  13  18  43  45     <
		           68   95

				
  7  13  18  43  45  56 <
		           68   95

				
  7  13  18  43  45  56  68  95 <----- テープ3
 
 この場合、磁気テープを余分に1本必要とすることに注意。

 上記基本原理を、1次元配列のデータに対して行なうために、データを2分割し、疑似的に2本の磁気テープを構成する。例を用いて、(内部的な)マージソートの動作を示そう。

入力データ n=2^3個とする。

      
     45   56   43   13   95   18   7    68
 
ステップ1
上記データを2つに分割する。

(45   56   43   13)(95   18   7   68)の2組のデータに分ける。
2組の各データをさらに分割する。
(45   56) (43   13)(95  18)(7   68)
  上記操作を2つのデータの組になるまで、繰り返す。

ステップ2
2つのデータの各組に対し、マージ操作を行なう。よって、 

(45   56)  と  (13   43) と (18   95)(7   68)
さらに、マージ操作を繰り返す。よって
(13   43   45   56)  と (7   18   68   95)
となる。さらに、マージ操作を行なう。  よって、

     7   13   18   43   45   56   68   95
 
となる。
   マージソートのプログラムを以下に示す。

 1:  void MergeSort( int data[], int left, int right ) {
 2:  	int mid;
 3:  
 4:  	if( left < right ) {
 5:  		mid = (right - left + 1) / 2;
 6:  		MergeSort( data, left, left+mid-1 );
 7:  		MergeSort( data, left+mid, right );
 8:  		Merge( data, left, left+mid );
 8:  	}
10:  }
11:  
12:  void Merge( int data[], int l, int m ) {
13:  	int tmp[MaxNumber+1], h, i, j, k, r;
14:  	
15:  	i = l;
16:  	j = m;
17:  	r = 2*m-l;
18:  	k = l;
19:  	while( (i < m) && (j < r) ) {
20:  		if( data[i] < data[j] ) {
21:  			tmp[k] = data[i];
22:  			i++;
23:  		}
24:  		else {
25: 			tmp[k] = data[j];
26:  			j++;
27:  		}
28:  		k++;
29:  	}
30:  	if( i < m )
31:  		for( h=i; h < m; h++ ) {
32:  			tmp[k] = data[h];
33:  			k++;
34:  		}
35:  	if( j < r )
36:  		for( h=j; h < r; h++ ) {
37:  			tmp[k] = data[h];
38:  			k++;
39:  		}
40:  	for( h=l; h < r; h++ )
41:  		data[h] = tmp[h];
42:  }	
 
 マージソートの計算時間量は、n*log(n)である。データが2個になるまでデータの2分割を繰り返していく。この分割は、log(n)回行なわれる。各ステージでは、並べ替えが行なわれ、その計算量はO(n)である。よって、全体でn*log(n)となる。

戻る

アプレットに戻る

a93sj030@j.dendai.ac.jp