離散システム特論整列(sorting)アルゴリズム１参考文献 1. 大森克史・木村春彦・広瀬貞樹著「アルゴリズムの基礎」共立出版(1997) 2. 渡邊敏正著「データ構造と基本アルゴリズム」共立出版(2000) 整列とは • 全順序集合Sが与えられたとき，Sのすべての要素をその全順序に従って並べ替えること． • 簡単のため，ｎ個の整数の集合をSとし，通常の数字の大小関係で小さい数から大きい数へ並べ替えるとする（昇順ソート ascending sort)．ソーティングアルゴリズム選択法（selection sort）データ列の最小値を選択し，未整列部分の先頭に置くことを順次繰り返す． ◆ min{a1, a2, … , an}とa1を交換 ◆ min{a2, …, an}とa2を交換．．． ◆ min{an-1, an}とan-1を交換選択法の擬似コード for (i=1; i≦n-1;i++){ min:= i; // 最小値の添字をしまう． for (j=i+1; i≦n; j++){ if(aj < amin) min :=j; } swap(ai, amin); } 選択法の例（４，１０，５，２，１，７，９，３，８，６）（１，１０，５，２，４，７，９，３，８，６）（１，２，５，１０，４，７，９，３，８，６）（１，２，３，１０，４，７，９，５，８，６）（１，２，３，４，１０，７，９，５，８，６）（１，２，３，４，５，７，９，１０，８，６）（１，２，３，４，５，６，９，１０，８，７）あとはよろしく選択法の計算量 n個のデータのソートに必要な最悪比較回数 for (i=1; i≦n-1;i++){ min:= i; // 最小値の添字をしまう． for (j=i+1; i≦n; j++){ if(aj < amin) min :=j; } swap(ai, amin); } Ｏ（？）バブルソート(bubble sort) 隣接する2項を比較し，aj > aj+1のように左の項が右の項よりもおおきければ，これを交換するという操作をデータ列の左から右へ走査することを順次続け，結果的に，右端から順にデータを確定させる．背の順に並ぶよバブルソートの擬似コード for (i = n; i 2; i++){ for (j=1; j i-1; j++){ if (aj > aj+1) swap (aj, aj+1); } } バブルソートの例（１）（４，１０，５，２，１，７，９，３，８，６） i j （４，１０，５，２，１，７，９，３，８，６） i j （４，５，１０，２，１，７，９，３，８，６） j i （４，５，２，１０，１，７，９，３，８，６） j あとはよろしく i （４，５，２，１，７，９，３，８，６，１０） i バブルソートの例（２）（４，５，２，１，７，９，３，８，６，１０） i j （４，５，２，１，７，９，３，８，６，１０） i j （４，２，５，１，７，９，３，８，６，１０） i j あとはよろしく（４，２，１，５，７，３，８，６，９，１０） i ．．．をつづける！バブルソートの計算量 n個のデータのソートに必要な最悪比較回数 for (i = n; i 2; i++){ for (j=1; j i-1; j++){ if (aj > aj+1) swap (aj, aj+1); } } Ｏ（？）ちょこっと工夫： j=1,…, i-1で入れ替えが一度もなければソート終了挿入法（insertion sort） a1からai-1がすでにソートされていると仮定して，aiをしかるべき正しい位置に挿入する．すなわち，aiよりも大きいデータを右側にシフトした跡，その空き場所にaiを挿入する．挿入法の擬似コード for(i = 2; i  n; i++){ w:=ai; j:=i; while(aj-1>w and j>1){ aj:=aj-1; //移動 j:=j-1; } aj:=w; } //挿入挿入法の例（４，１０，５，２，１，７，９，３，８，６） j-1 W=10 （４，１０，５，２，１，７，９，３，８，６） j-1 W=5 （４，１０，１０，２，１，７，９，３，８，６） j-1 W=5 （４，５，１０，２，１，７，９，３，８，６） j-1 W=5 （４，５，１０，２，１，７，９，３，８，６） j-1 W=２あとはよろしく挿入法の計算量 n個のデータのソートに必要な最悪比較回数 for(i = 2; i  n; i++){ w:=ai; j:=i; while(aj-1>w and j>1){ aj:=aj-1; //移動 j:=j-1; } aj:=w; } //挿入Ｏ（？）挿入法の計算量（続） for(i = 2; i  n; i++){ w:=ai; j:=i; while(aj-1>w and j>1){ aj:=aj-1; //移動 j:=j-1; } aj:=w; } //挿入ちょこっと工夫：リスト構造を用いれば，挿入場所を移動をしなくてもよい．でも挿入場所をみつけるのに，おなじだけwhileをまわす？挿入法の計算量（続々） n個のデータのソートに必要な平均比較回数場合 Whileの反復回数 ai<a1 i-1回 a1ai<a２ i-2回．．．各場合が等確率に起こるとすると，．．． ai-2ai<ai-1 1回 ai-1ai 0回 i1 1  n i 1 1  i k  2  4 n(n 1)  i 2 i 2 k 0 n Selection/Bubble/Insertionの比較長所選択法バブル挿入法短所ヒープソート（heap sort）選択法で最小値をみつけるときに，ヒープを用いて効率よく行う．ヒープ： ◆ 最小値をO(1)でみつける． ◆ 最小値を削除してヒープ構造を保つのに，O(log ｋ)でできる．（ｋはヒープの中の要素数）ヒープ根付き２分木：根をもつ（親子関係のある）木で各頂点の子が２個以下．完全２分木：頂点を左詰で並べた根付き２分木． •すべて葉は根からの深さが高々1 しか違わない．（深さmか，m-1に葉がある） •深さmの葉は左詰め． •深さがm-2以下の頂点は子をちょうど２つもつ．ヒープ： ◆ 完全２分木 ◆ 各頂点がデータを持つ ◆ 親頂点のデータは子頂点のデータよりも小さい d-ヒープ：子がd個以下の完全d分木からなるヒープ．単にヒープというと，2-ヒープを指す．ヒープかな？図の上下が親子関係を表す１１３５２４４３７１２６５４５７６１１２３６３２５８３６３７５８２６３５ヒープソートの擬擬似コード 1: {a1, …, an}をヒープ化； 2: for(i=1;in-1; i++){ 3: ヒープから最小値を取り出して，aiと入れ替え； 4: {ai+1, …, an}を再ヒープ化； 5: } •最小値はヒープの •１行目と３行目は．．．にあるので，３行目はＯ（）でできる． DeleteMin（１）１．最小値を根からとる．１２３７根のデータがない！５８６ DeleteMin（２）２．とりあえず，最後のデータを移動６２３７５８６親子のデータの大きさ関係が崩れる DeleteMin（３）３．ダウンヒープ ajで親子のデータの大小関係が崩れているとする．（１）ajの子のデータの小さい方をaiとする（２）aj<aiならば，ajとaiを入れ替える．（３）これを子がなくなるか，あるいはどの子よりもajが小さくなるまで繰り返す．６２２３７５８２６３７５８３６７なぜ，小さい子どもと入れ替えるの？５８ヒープソートの操作 1: {a1, …, an}をヒープ化； 2: for(i=1;in-1; i++){ 3: ヒープから最小値をみつけてi番目に格納； 4: DeleteMin；１ 5: } １行目は？ //最小値をヒープから取り除く６２５２５３７８６３７８２６５３７８２３５６７８ヒープの初期化データ数nが既知 1. １頂点からなる完全２分木をn個作り，データを割り振る． 2. 以下の走査を繰り返して１つのヒープにする２つのヒープがあるときに，新しい1点wを根として，これらのヒープを部分木とするような完全2分木から 1つのヒープを作る．このとき，ダウンヒープの走査でヒープの条件を満たすようにする．ヒープの初期化操作の例（１）（４，１０，５，２，１，７，９，３，８，６）のヒープをつくる１．とりあえず，データを入れる４５ 10 ２３１８６７９ヒープの初期化操作の例（２） 10 ２．ダウンヒープを繰り返す２４ダウンヒープ１７８６１２９３３８５ 10 ２ＯＫ３１８６ＯＫ 10 ６ 1 ２３８ 10 6 ヒープの初期化操作の例（3）２．ダウンヒープを繰り返すダウンヒープ４５ 1 ２３ 6 ８ 10 ７９ 1 ＯＫ 3 4 ５ 2 6 ８ 10 ７９ヒープソートの計算量 1: {a1, …, an}をヒープ化；Ｏ（ヒープの深さ） 2: for(i=1;in-1; i++){ 3: ヒープから最小値をみつけてi番目に格納；Ｏ（１） 4: DeleteMin； //最小値をヒープから取り除くＯ（ヒープの深さ） 5: } １６２５２５３７８６３７８２６５３７８ k個のデータを格納するヒープの深さは？２３５６７８ヒープの深さ k個のデータを格納するヒープの深さは？深さ０ 1 深さ１５ 2 3 4 6 ８７９ 10 深さ２深さ３深さiに格納できるデータの個数は？深さｄのヒープ全体に格納できるデータの個数は？ 2d+1-1 2d-1<k2d+1-1を満たす．よって， 2dk<2d+1. すなわち，d=|_ log k 」ヒープソートの計算量(続) 1: {a1, …, an}をヒープ化；Ｏ（要素数 × ヒープの深さ） 2: for(i=1;in-1; i++){ 3: ヒープから最小値をみつけてi番目に格納；Ｏ（１） 4: DeleteMin； //最小値をヒープから取り除くＯ（log (n-i)） 5: } Totalで４行目： log(n-1)+log(n-2)+…+log(1)=log( (n-1)! ) n log n 1行目もO(n log n)は明らか．ちゃんと算定すると，O(n) ヒープソートの計算量：Ｏ（）ヒープの初期化はO(n) ただし，データ数nは既知 (n=2d-1と仮定) ヒープの大きさヒープの数ダウンヒープの回数１（葉に対応）２d 0 3 ２d-１ 1 … … … n=2d -1 1 = 20 d Total: ２d-１+2・２d-２ +３・２d-３ +．．． +ｄ・２０= ２d+１-d-2 = O(n) ヒープソートの例（４，１０，５，２，１，７，９，３，８，６）のヒープをつくる 1 ５ 2 6 ７ 3 4 10 ５ 2 ９８ 10 10 6 ７ 4 10 ８ 3 ５ 4 ５ 6 ７９８８ 4 ５ 3 6 ７ 3 4 3 2 8 ９ 10 6 ７９あとはよろしく９完全２分木の実現 ◆ 構造体：各頂点が親，子へのポインタを持つ． ◆ 配列：順番に格納１２４８３５６Ａ＝１２３７Ａ［ｉ］の子はA[2i] とA[2i+1] 親は，A[└i/2」] ４５６７８