| 目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|

整列アルゴリズム(2)

前回は,ソートアルゴリズムの中から比較的単純な 3 つのアルゴリズム,す なわちバブルソート,選択ソート,挿入ソートについて説明した.今回は以下 表の中であげられている計算時間がO(nlogn)であると評価される高速アルゴリ ズムについて説明する.

表1 整列アルゴリズムの種類

分類 低速アルゴリズム 高速アルゴリズム
選択法 単純選択ソート ヒープソート
挿入法 単純挿入ソート シェルソート(注意*1)
交換法 バブルソート クイックソート
併合法 ・・・ マージソート
注意*1:シェルソートを高速アルゴリズムに分類したが,計算量はO(n^1.2)で あることが知られている.

ヒープソート(Heapsort)

ヒープ(heap)とは,以下の条件を満たす2分木のことである.2分木とは,1 つの頂点から2本以下の枝が出ている木のことであり,計算機分野では重要な 構造の1つである.ヒープを構成する2分木の各頂点には次の2式を満たさな ければならない.
  1. h(i) ≧ h(2i) i=1,2,3,...
  2. h(i) ≧ h(2i+1) i=1,2,3,...
つまり,2分木の各頂点に位置するデータの値は,常に上に位置するデータの 値以下になっていなければならない.
 例
               h(1)
                           |
          |−−−−−−−−−−−−−−−−−−|
         h(2)         h(3)
        |−−−−−+−−−−−|      |−−−−−+−−−−−|
   h(4)    h(5)         h(6)            h(7)
  |−−+−−|     |−−+−−|
h(8)    h(9)   h(10)

 この場合,h(1)≧h(2),h(3)
       h(2)≧h(4),h(5)
      h(3)≧h(6),h(7)
      h(4)≧h(8),h(9)
      h(5)≧h(10)
である.ヒープによる並べ換えは,ヒープがすでに与えられているものとして,ヒープが空になるまで以下の2つのステップを繰り返す.
ステップ 1
最上位のh(1)を取り出す.
ステップ 2
残りのヒープh(2),h(3),...,h(n)をヒープに再構成する. 再構成は,以下の1), 2) にしたがって行なう.
  1. h(1)の位置にh(n)を移動する.もとのh(n)は削除する.
  2. h(1)の位置からshiftdown操作を行なう.
    shiftdown操作
    h(i) < max(h(2i), h(2i+1))のとき,h(2i)とh (2i+1)の大きい方をh(i)と交換する.交換したところか ら,同様な操作を繰り返す.
shiftdown操作の例を以下に示す.
初期状態:
              84
         |−−−−−+−−−−−|
         73     66
     |−−−+−−−|   |−−−+−−−|
    22    37  11     49 
  |−−+−−|
  
 
状態2:初期状態においてh(1)である84を取り出し,h(n)である6をh (1)の位置に移動する.
                     −−−>84
         |−−−−−+−−−−−|
        73       66
     |−−−+−−−|   |−−−+−−−|
     22   37  11   49 
  |−−+−−|

  
h(1)の位置(6)からshiftdown操作を行なう.


             73       −−−>84
         |−−−−−+−−−−−|
                66
     |−−−+−−−|   |−−−+−−−|
     22   37  11   49 



             73       −−−>84
         |−−−−−+−−−−−|
         37      66
     |−−−+−−−|   |−−−+−−−|
     22     11   49 

状態3:h(1)である73を取り去り,h(n)である49をh(1)の位置に移動する.

            49       −−−> 73 84
         |−−−−−+−−−−−|
         37      66
     |−−−+−−−|   |−−−+−−−|
     22   6   11     

 h(1)からshiftdown操作を行なう.

            66       −−−> 73 84
         |−−−−−+−−−−−|
         37       49
     |−−−+−−−|   |−−−+−−−|
     22   6   11     
 
状態4:66を取り除き,11をh(1)位置に移動し,shiftdown操作を行なう.

            49       −−−> 66 73 84
         |−−−−−+−−−−−|
         37      11
     |−−−+−−−|   
     22   6        

状態5:以下同様な操作を繰り返す.

          37       −−−> 49 66 73 84
       |−−−−−+−−−−−|
       22      11
   |−−−+−−−|   
   6             

状態6:

       22       −−−> 37 49 66 73 84
    |−−−−−+−−−−−|
    6       11

状態7:

       11    −−−> 22 37 49 66 73 84
    |−−−−−+−−−−−|
    6 

状態8:

          −−−> 11 22 37 49 66 73 84
    |−−−−−+−−−−−|
 
よって,取り除かれたデータは並べ換えが済んでいる.

次に,最初のヒープを構成する方法について述べる.

ステップ1
任意の2分木を与える.この2分木の各頂点のデータの値をそれぞれ h(1),h(2),h(3)...とする.
ステップ2
この2分木で,枝が1本も出ていない頂点,つまりh(k),h(k+1),... (k=[n/2]+1)は,下位にデータを持たないため,ヒープの条件が満足されてい ると解釈できる. 
ステップ3
残りの頂点をh(k-1),h(k-2),...,h(1)の順にとりあげ,その頂点を 下位の部分木の根(h(1))とみたてヒープを構成していく.その際には, 前記のshiftdown操作を使う.

ヒープ生成の例

初期状態:
             21
         |−−−−−+−−−−−|
        53       12
     |−−−+−−−|   |−−−+−−−|
     46   87  59    40 
  |−−+−−|
 70
状態2:初期状態において70,40,59,87は下位にデータを持たない ので,ヒープの条件を満足していると考えられる.まず,46を2分木の根と みたてshiftdown操作を行なう.
             21
         |−−−−−+−−−−−|
         53        12
     |−−−+−−−|   |−−−+−−−|
    70      87  59    40 
  |−−+−−|
  46
 
状態3:状態2において70,87,59,40,46は,ヒープの条件を満 足していると考えられる.次に12を2分木の根とみたてshiftdown操作を行 なう.
             21
         |−−−−−+−−−−−|
         53        59
     |−−−+−−−|   |−−−+−−−|
     70    87  12     40 
  |−−+−−|
  46
状態4:状態3において59,70,87,12,40,46は,ヒープの条 件を満足していると考えられる.次に53を2分木の根とみたてshiftdown操 作を行なう.
             21
         |−−−−−+−−−−−|
         87       59
     |−−−+−−−|   |−−−+−−−|
     70    53  12     40 
  |−−+−−|
  46
状態5:状態4において87,59,70,53,12,40,46は,ヒー プの条件を満足していると考えられる.次に21についてshiftdown操作を行 なう.
             87
         |−−−−−+−−−−−|
         70     59
     |−−−+−−−|   |−−−+−−−|
     46    53  12     40 
  |−−+−−|
  21
よって,任意に与えた2分木に対して,ヒープが構成できた.

上記で説明した考えをもとに,データの並べ換えを行なう.実際に計算機で行 なう場合,2分木を表現することは面倒なことである.そこで,今回は配列を 工夫し2分木にみたてておこなう.下記のような配列を考えてみよう.

   ------+-----+-----+-----+-----+-----+-----+-----+-----+----
  |h(1)|h(2) h(3)|h(4) h(5) h(6) h(7)|h(8) h(9)・・・
     ------+-----+-----+-----+-----+-----+-----+-----+-----+----
便宜的に,配列の区切りを入れている所と入れていない所がある.これは,2 分木の階層を明らかにするためである.上記配列は,下記の2分木を表現して いることを理解していただきたい.
                 h(1)
                          |
          |−−−−−−−−−−−−−−−−−−|
          h(2)        h(3)
        |−−−−−+−−−−−|      |−−−−−+−−−−−|
   h(4)    h(5)         h(6)            h(7)
  |−−+−−|     |−−+−−|
 h(8)    h(9)   h(10)
アルゴリズムの進行とともにヒープが縮小するため,配列の後尾が空となる. そこで,ヒープから取り出したデータを配列の後ろから順に詰めて行くことに より,ソートが完了した時点で,配列内にデータが並べ替わっていることにな る.

配列の場合の例

(1)初期ヒープの生成

初期データ:

 	21 | 53  12 |  46  87  59  40 | 70
状態2:初期状態において70,40,59,87は下位にデータを持たない ので,ヒープの条件を満足していると考えられる.まず,46を2分木の根と みたてshiftdown操作を行なう.
	21 | 53  12 | 70  87  59  40 | 46
状態3:状態2において70,87,59,40,46は,ヒープの条件を満 足していると考えられる.次に12を2分木の根とみたてshiftdown操作を行 なう.
	21 | 53  59 | 70  87  12  40 | 46
状態4:状態3において59,70,87,12,40,46は,ヒープの条 件を満足していると考えられる.次に53を2分木の根とみたてshiftdown操 作を行なう.
	21 | 87  59 | 70  53  12  40 | 46
状態5:状態4において87,59,70,53,12,40,46は,ヒー プの条件を満足していると考えられる.次に21を2分木の根とみたて shiftdown操作を行なう.
          87 | 70  59 | 46  53  12  40 | 21
(2) ソート

初期状態:

	87 | 70  59 | 46  53  12  40 | 21
状態2:先頭の87(h(1))を取り出しす. 21(h(k))を2分木の根(h (1))に移動し,shiftdown操作を行なう. 取り出した87は配列の最後に格 納する.[$記号以降は整列済み]
	70 | 53  59 | 46  21  12  40 $ 87
状態3:先頭の70(h(1))を取り出しす.40を2分木の根(h(1))に移動し, shiftdown操作を行なう. 取り出した70は配列の最後から2番目にに格納 する.
	59 | 53  40 | 46  21  12 $ 70  87
状態4:先頭の59(h(1))を取り出す.12を2分木の根(h(1))に移動し, shiftdown操作を行なう.取り出した59は配列の最後から3番目に格納する.
	53 | 46  40 | 12  21 $ 59  70  87
状態5:以下同様な操作を繰り返す.
	46 | 21  40 | 12 $ 53  59  70  87
状態6:
	40 | 20  12 |$ 46  53  59  70  87
状態7:
        21 | 12 $ 40  46  53  59  70  87
状態8:
	12  21  40  46  53  59  70  87
上記の考えをプログラムすると,次のようになる.
53	    //ヒープソート
54	    static void sortArray(int[] array){
55		//初期ヒープの作成
56		int bottom = ■■■■■■ ;
57		int top =    ■■■■■■ ;
58		while( ■■■■ ) {
59		    shiftDown(array, ■■, ■■);
60		    ■■■;
61		}
62		
63		//ヒープの再編成
64		while( ■■■■ ) {
65		    int tmp = array[0];
66		    array[0] = array[top-1];
67		    array[top-1] = tmp;
68		    ■■■;
69		    shiftDown(array, ■■, ■■);
70		}	
71	    }
72	    /*
73	    shiftdown 操作を行うメソッド
74	
75	    array と言う名前の整数配列をtop番目の要素を最終接点,
76	    bottom番目の要素を木の根と見なしてヒープを再構成.
77	    arrayは Javaの配列なので0,1,2,..として順に参照する
78	    ヒープ木では1,2,3,...と参照する方が便利なため"-1"している
79	    */
80	    static void shiftDown(int[] array, int top, int bottom){
81		int i = 2* bottom;
82	
83		while( i <= top ) {
84		    if( i < top && array[(i+1)-1]> array[i-1]) {
85			i++;
86		    }
87		    if( array[bottom-1] >=array[i-1] ) {
88			break ;
89		    }
90		    int tmp = array[bottom-1];
91		    array[bottom-1] = array[i-1];
92		    array[i-1] = tmp;
93		    bottom =i ;
94		    i = 2 * bottom;
95		}
96 }
56〜61で初期のヒープを作成し,64〜70でヒープの再構成を行なっている.ヒー プソートの計算時間量は,O(nlogn)である.簡単に,理由を述べる.主に関数 shiftdown内の入れ換えの回数に着目してやればよい.つまり,90〜93の実行 回数である.2分木の根から順に,下位の部分木の頂点にあるデータと比較す るため,1回のshiftdown操作では,log(n)回(logとは対数関数であり,この 場合2分木であるため対数の底を2として考えている.nはデータの個数であ る.)比較を行なっていることになる.関数shiftdownの呼ばれる回数は,デー タの個数nに比例している.そのため,n*log(n)が得られる.基本的な考え方 は以上の通りである.
ヒープソートは,クイックソートに比べて平均約2倍のスピードを要する.し かしながら,ヒープソートは,どのような配置のデータにも常にO(nlogn)で処 理がなされ,外部記憶装置内のデータにも適用可能なことから,利用度の高い アルゴリズムであるといえる.

シェルソート(Shellsort)

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

例を用いて,シェルソートの動作を示そう.

入力データ
  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/2にして求めているが,任意でよいが, なるべく互いに素(割り切れない)の数を選ぶとよい.この幅の取り方によって データの入れ替え回数が変わることが知られている.D.E.Knuthは,以下のよ うな数列で分割の幅を採用すると効率がよいことを示した.
  1, 4, 13, 40, 121, ..
一般的にS[i+1] = 3 * S[i] +1, S[1]=1で得られる数列を逆順にとるものとする.こ れらの数値は,互いに素ではないが,より効率的であることが知られている. シェルソートの計算時間量は,分割の幅の取り方によりO(n^1.2)からO(n^2)で あることが,知られている.証明については,難しいため省略する.

クイックソート(Quicksort)

クイックソートは世の中で最も速いソートアルゴリズムとして知られている. (これは一つのCPUで順次処理を行なった場合である.最近では計算機の機 能が高まり並列処理や分散処理が可能となっているため,複数のCPUを持っ た計算機上での並べ換えについては,クイックソートよりも速いアルゴリズム が提案されている.)

クイックソートは,データの分割法をソートのアルゴリズムに適用した典型な ものである.データ分割法の基本原理は,

  1. データのブロック分割
  2. 各ブロックごとの処理(並べ換え)
  3. ブロックの統合
であり,クイックソートでは特に1のデータの分割にアルゴリズムのよさの秘 密が隠されている.例を用いてクイックソートのアルゴリズムを解説しよう.
48 65 10 36 83 5 21 72
ステップ01
まず与えられたデータ列の真ん中(左から4番目)に位置するデータを基準値を して定める.例では,36と基準値としよう.
48   65   10   36   83    5   21   72
ステップ02
データを左から順に基準値よりも大きいデータを捜す.まず48が見つかる.続 いて,右から順に基準値よりも小さいデータを捜す. 21が見つかる.ここで, 48と21を入れ替えする.現在注目しているデータの位置を次に進める(左から 見ている場合は一つ右へ,右からの場合は左へ一つ進める).
21   65   10   36   83    5   48   72
さらに,ステップ02を続けると,5と65が入れ替わる.
21    5   10   36   83   65   48   72
以下,同様な操作を繰り返し,注目している点が交差するまで行なう.すると
21    5   10   36   83   65   48   72
が得られる.これは,基準値とした位置(左から4番目)を境に,左右ブロック に分割したことになる.左側には4番目のデータ(36)よりも小さいデータ,右 側には大きいデータとなる.

ステップ1-1
左側のブロックに対して,ステップ01,02を行なう.

21       5     10  

5  |   21     10  
よって,5と21,10とに分割できる.

ステップ1-1-1
さらに,左側についてステップ01,02を行なう.この場合5だけなのでなにもし ない.

ステップ1-1-2
右側の21,10についてステップ01,02を行なう. 上記ステップ1-1-1,1-1-2により,

5   10   21
が得られる.

ステップ1-2
83,65,48,72について同様にステップ01,02を行なう.よって,

5   10   21   36   48   65   72   83 
が得られる.

Quicksortは再帰的なアルゴリズムとなっている.先に示した例のデータを用い て実行の様子を表現すると,下記のような構造となっている.

	 (  48  65  10  36  83  5  21  72  )
              |
             |QuickSort(1,8)
            −−−−− +−−−−−−−
       |     |       |
 	( 21  5  10 )  ( 36 )  (  83  65  48  72 )
        |                         |
QuickSort(1,3)|                        |QuickSort(5,8)
        −−− +−−           −−+−−−−
   |      |         |             |
    ( 5 )      ( 21 10 )       ( 48 ) ( 65 )   ( 83 72 )
          |                   |
   QuickSort(2,3)|                            |QuickSort(7,8)
               −−+−−               −−+−−
       |    |              |    |
      ( 10 )    ( 21 )                ( 72 )    ( 83 )
よって分割したブロックを統合すると,
5   10   21   36   48   65  72   83 
となる.

マージソート(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
ステップ2
上記データを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
となる.
  マージソートの計算時間量は,n*log(n)である.データが2個になるまでデー タの2分割を繰り返していく.この分割はlog(n)回行なわれる.各ステージで は,並べ替えが行なわれ,その計算量はO(n)である.よって,全体でn*log(n) となる.

課題

  1. (必須)ヒープソートのアルゴリズムを完成し,実行してみる.(配列の長さはarray.length)
  2. 先週分の課題で未完成のアルゴリズムがあればそれを完成させる.
  3. (余裕があれば)今週紹介したクイック,マージ,シェルの各ソートを作ってみる.

| 目次| 1234567891011121314
| 資料| 予定| 課題| 宿題|