Explain Sort Algorithms  

高速アルゴリズム

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

シェルソート ( Shellsort )

 シェルソートは、分割法を適用したひとつの方法である。基本的な考え方は、与えられたデータをいくつかのブロックに分割し、そのブロックに対し単純挿入法を行なうもである。データをいくつかのブロックに分割し大ざっぱな並べ替えを繰り返しながら、最終的には全データに対して並べ替えをする。このように分割することによって、データの入れ替えの回数を少なくすることを、D.Shellによって考えられ、シェルソートの名前が付いた。
 例を用いて、シェルソートの動作を示そう。
入力データ

  45   56   13   43   95   18   7    68

ステップ1 
分割の幅をskip=4とし、上記データをいくつかのブロックに分割する。

  45   56   13   43   95   18    7   68
   ^    ^    ^    ^    ^    ^    ^    ^
   |    |    |    |    |    |    |    |
  B1   B2   B3   B4   B1   B2   B3   B4 <--- 便宜上ブロックに名前を付けた

  このブロック内で並べ替えをおこなう。

    B1ブロック   45  95   ---->   45  95
    B2ブロック   56  18   ---->   18  56
    B3ブロック   13   7   ---->    7  13
    B4ブロック   43  68   ---->   43  68
  よって、
	45   18   7   43   95   56   13   68
  となる。
ステップ2 分割の幅を1/2にする。skip=2としてブロックに分割する。

	45   18   7   43   95   56   13   68
	 ^    ^    ^    ^    ^    ^    ^    ^
         |    |    |    |    |    |    |    |
         B1   B2   B1   B2   B1   B2   B1   B2

  このブロック内で並べ替えを行なう。

    B1ブロック  45    7   95   13   ---->   7   13   45   95
    B2ブロック  18   43   56   68   ---->  18   43   56   68
  よって、
	7   18   13   43   45   56   95   68
    となる。
ステップ3 分割の幅をさらに1/2にする。skip=1となり、全データを一つのブロック     として考える。    よって、

	7   13   18   43   45   56   68   95
となり、並べ替えが完了する。  上記分割の幅の取り方は任意でよいが、ステップを増すごとに幅が減少していなければならない。最後のステップでは、skip=1として必ず全データを一つのブロックとして並べ替えを行なわなければならない。
 シェルソートのプログラムを以下に示そう。

 1:  void ShellSort(int data[], int n)  {
 2:  	int i, skip;
 3: 
 4: 	skip = n / 2;
 5:	while( skip > 0 ) {
 6: 		Insertionsort( data, skip, n );
 7: 		skip = skip / 2;
 8: 	}
 9: }
10: 
11:  void Insertionsort(int data[], int skip, int n) {
12:  	int tmp, i, j;
13:  
14:  	for (i=skip; i < n; i=i+skip)
15:  		for (j=i-skip; j >= 0; j=j-skip)
16:  			if(data[j] > data[j+skip]) {
17:  				tmp = data[j];
18:  				data[j] = data[j+skip];
19:  				data[j+skip] = tmp;
20:  			}
21:  }
 11〜21は、単純挿入法のメソッドである。単純挿入ソートで紹介したメソッドと別なものをここでは紹介した。一見バブルソートに外観が似ているが、基本的な考え方は単純挿入法であることに注意しよう。ただし、変数skipを用いて1次元的なデータをskip個おきに取っていくことによって、ブロックに分割しているように扱っている。
1〜9では、分割の幅をデータの個数の半分を初期値として、幅が1になる値を1/2にして単純挿入法を繰り返している。

 上記シェルソートでは、分割の幅を1/2にして求めているが、任意でよいが、なるべく互いに素(割り切れない)の数を選ぶとよい。この幅の取り方によってデータの入れ替え回数が変わることが知られている。
 D.E.Knuthは、以下のような数列で分割の幅を採用すると効率がよいことを示した。


     1、4、13、40、121、..
一般的に、Si+1 = 3*Si +1, S1=1 で得られる数列を逆順にとるものとする。これらの数値は、互いに素ではないが、より効率的であることが知られている。  次のプログラムは、上記Knuthが推奨する数列で得られた数値を分割幅に採用した例である。

 1:  void ShellSort(int data[], int n) {
 2:   	int i, skip[] = {121,40,13,4,1};
 3:  
 4:  	for ( i=0; i < 5; i++ )
 5:  		Insertionsort( data, skip[i], n );
 6:  }
 7:  
 8:  void Insertionsort(int data[], int skip, int n) {
 9:  	int tmp, i, j;
10:  
11:  	for (i=skip; i < n; i=i+skip)
12:  		for (j=i-skip; j >= 0; j=j-skip)
13:  			if(data[j] > data[j+skip]) {
14:  				tmp = data[j];
15:  				data[j] = data[j+skip];
16:  				data[j+skip] = tmp;
17:  			}
18:  }
 シェルソートの計算時間量は、分割の幅の取り方によりO(n^1.2)からO(n^2)であることが、知られている。証明については、難しいため省略する。

戻る

アプレットに戻る

a93sj030@j.dendai.ac.jp