大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp 再帰 データ構造とプログラミング（８） 大岩 元 慶応大学環境情報学部 ohiwa@sfc.keio.ac.jp
マージソート ソート済みの２つの配列をマージして１つのソート済み配列にする 未ソートの配列を２つの未ソート配列に分解する作業を再帰的に繰り返すと、最後は１つの要素から成る配列（ソート済）となる ２つに分解した再帰から帰ってきた所で、マージすれば、ソート済みとなる 作業用配列を必要とするが、Ｏ（ｎ*ｌｏｇ（ｎ））で処理できる
マージソートのプログラム public void mergeSort(){ double[ ] workSpace = new double[nElems]: recMergeSort(workspace, 0, dElems-1); } private void recMergeSort( double workspace, int lowerBound, int upperBound){ { if (lowerBound == upperBound) return else {int mid = (lowerBound + upperBound)/2: //中間点を見つける recMergesort( workspace, lowerBound, mid); //下半分をソートする recMergeSort( workspace, mid+1, upperBound): //上半分をソートする merge(work]space, lowerBound, mid+1, upperBound);//マージする
マージのプログラム private void merge( double[ ] workSpace, int lowPtr, int highPtr, int upperBound){ int j = 0; int lowerBound = lowPtr; int mid = highPter-1; int n = upperBound – LowerBound + 1; while( lowPtr <= mid && highPtr <= upperBound) if( theArray[lowPtr] < theArray[highPtr]) workSpace[j++] = theArray[lowPtr++] else workSpace[j++] = theArray[highPtr++]; while( lowPtr <= mid) workSpace[j++] = theArray[lowPtr++]; while( highPtr <= upperBound) workSpace[j++] = theArray[highPtr++]; for (j = 0; j < n; j++) theArray[loweBound + j] = workSpace[j];
マージソートの効率（２**ｎ個の時） コピー回数は、配列から作業配列へと、その反対へ、それぞれ ｎ*ｌｏｇ（ｎ） 回となる 各マージで（ｍ個の要素）、最大比較回数は ｍ－１、最小比較回数はｍ／２ コピーもマージも、Ｏ（ｎ*ｌｏｇ（ｎ））
再帰の自己関理 再帰呼び出しが行なわれると、引き数と帰り先がスタックにプッシュされる 呼ばれたメソッドはスタックを見て、引き数を得る メソッドが終ると、スタックから帰り先をポップし、そこに戻る。引数はポップして捨てる
クイックソート ピボットを配列の中から任意（例題では右端）に選ぶ ピボットより大きな要素を右に、小さな要素を左に入れる(分割 partition) 右側と左側をそれぞれ、再帰的に呼び出す 分割が左右均等にできれば、計算時間はO(n*log(n)) 分割が常に片寄ると、O(n*n)になってしまう
クイックソートの主要部 public void recQuickSort( int left, int right){ if (right-left <= 0) return; else{ double piivot = theArray[ right]; int partition = partitionIt( left, right, pivot); recQuickSort( left, partition-1); recQuickSort( partition+1, right); }
分割(partition) public int partitionIt(int left, int right, double pivot){ int leftPtr = left – 1; int rithPtr = right; while(true){ while( theArray[++leftPtr] < pivot) //NOP while( rightPtr > 0 && theArray[--Ptr] > pivot) //NOP if (leftPtr >= rightPtr) break; else swap( leftPtr, rightPtr) } swap( leftPtr, right); return leftPtr;