Document

再帰
データ構造とプログラミング（８）
大岩元
慶応大学環境情報学部
[email protected]
マージソート
ソート済みの２つの配列をマージして１つの
ソート済み配列にする
未ソートの配列を２つの未ソート配列に分解
する作業を再帰的に繰り返すと、最後は１つ
の要素から成る配列（ソート済）となる
２つに分解した再帰から帰ってきた所で、
マージすれば、ソート済みとなる
作業用配列を必要とするが、Ｏ（ｎ*ｌｏｇ（ｎ））で
処理できる
マージソートのプログラム
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;
}

Download Report