アルゴリズム導論学習ノート4---高速ソートとランダム化アルゴリズム
4535 ワード
アルゴリズムの特徴:
1.分治法設計
2.メモリの節約
3.非常に実用的
アルゴリズムプロセス:
ソートする配列をA[0]......A[N-1]とし、まず任意のデータ(通常は最初のデータ)をキーデータとして選択し、それより小さい数をすべて前に置き、それより大きい数をすべて後ろに置くプロセスを高速シーケンスと呼ぶ.なお、高速ソートは安定したソートアルゴリズムではなく、すなわち、複数の同じ値の相対位置がアルゴリズムの終了時に変動する可能性がある.
1回の高速ソートのアルゴリズムは、次のとおりです.
1)2つの変数I,Jを設定し,ソート開始時:I=0,J=N-1;
2)キーデータとして最初の配列要素を用いてkey,すなわちkey=A[0];
3)Jから前方探索を開始し、すなわち後から前方探索を開始し(J=J-1)、keyより小さい最初の値A[J]を見つけ、keyと交換する.
4)Iから後方探索を開始し、すなわち前から後方探索を開始し(I=I+1)、keyより大きい最初のA[I]を見つけ、keyと交換する.
5)I=Jになるまで、3、4、5のステップを繰り返す.(3,4ステップは、プログラム中に見つからなかったときj=j-1,i=i+1であり、見つかるまで.見つけて交換したときi,jポインタの位置は変わらない.また、i=jの場合、このプロセスはちょうどi+またはj-が完了した最後の別のループが終了するに違いない.)
例えば、ソートされる配列Aの値は、(初期キーデータ:X=49)キーXが永遠に変わらないことに注意し、常にXと比較し、どんな位置でも、最後の目的はXを真ん中に、小さいものを前に大きく後ろに置くことです.
A[0] A[1] A[2] A[3] A[4] A[5] A[6]:
49 38 65 97 76 13 27
初回交換後:27,3865,97,7613 49
(アルゴリズムの3ステップ目に従って後で探します)
2回目の交換後:27,38,49,97,763,65
(アルゴリズムの第4ステップに従って前から>Xの値を探し、65>49、両者を交換し、この場合:I=3)
3回目の交換後:27,38,13,97,765
(アルゴリズムの5ステップ目に従ってアルゴリズムを再び実行する3ステップ目を後で探します
4回目の交換後:27,38,13,49,76,765
(アルゴリズムの第4のステップに従って、前からXより大きい値を探し、97>49、両者を交換し、この場合:I=4、J=6)
このとき第3のステップが実行されるとI=Jとなり、1回の高速ソートが終了すると、1回の高速ソート後の結果は、27,38,13,49,76,9765、すなわち、49より大きいすべての数が49の後にあり、49より小さいすべての数が49の前にある.
へんしゅアルゴリズム
クイックソート(Quicksort)には、いくつかの特筆すべき変種アルゴリズムがあります.ここでは、いくつかの簡単な説明を行います.
ランダム化されたクイック・ソート:クイック・ソートの最悪の状況は、各分割によるプライマリ・エレメントの選択に基づいています.基本的なクイックソートは、最初の要素をマスターとして選択します.これにより,配列が秩序化された場合,分割ごとに最悪の結果が得られる.比較的一般的な最適化方法は、ランダム化アルゴリズム、すなわち、要素をホストとしてランダムに選択することである.この場合,最悪はO(n^2)であるが,最悪は入力データに依存するのではなく,ランダム関数の値取りが悪いためである.実際,ランダム化高速ソートにより理論的最悪の場合が得られる可能性は1/(2^n)にすぎない.従って、ランダム化された高速ソートは、ほとんどの入力データに対してO(nlogn)の所望の時間複雑度に達することができる.ある先輩は「ランダム化された迅速なソートは、一生の人柄のニーズを満たすことができる」と透徹した総括をした.
ランダム化の迅速なソートの唯一の欠点は、入力データに同じデータがたくさんあると、ランダム化の効果が直接弱まることです.限界の場合,すなわちn個の同じ数の並べ替えでは,ランダム化された高速並べ替えの時間的複雑さはO(n^2)に間違いなく低下する.解決策は,交換なしでメタが元の位置に残るように走査する方法である.
バランスエクスプレス(Balanced Quicksort):可能な限り中値を表す要素をキーデータとして選択し、通常のエクスプレスの原則に従って比較、置換、再帰する.通常、このデータを選択する方法は、先頭、末尾、中間の3つのデータを取り、その中の中値を比較して選択することである.この3つの値をとる利点は,実際の問題(例えば情報学コンテスト…)では,近似順序データや逆順序データが出現する確率が高く,このとき中間データは必然的に中値となり,事実上の近似中値でもある.万一、ちょうど中央の大きい2辺の小さい(あるいは逆)データに出会って、取った値はすべて最値に近いならば、少なくとも2つの部分を分けることができるため、実際の効率も2倍ぐらい増加することができて、その上データを少し乱して、退化の構造を破壊するのに有利です.
外部クイックソート(External Quicksort):通常のクイックソートとは異なり、キーデータはbufferであり、まず前と後のM/2要素をbufferに読み込み、そのbufferの要素をソートし、次にソートされた配列の先頭(または末尾)から次の要素を読み込みます.この要素がbufferの最小要素より小さい場合、最初の空席に書きます.この要素がbufferの中で最大の要素より大きい場合、最後の空席に書きます.そうでなければbufferの最大または最小の要素を配列に書き込み、この要素をbufferに配置します.最大値がこれらのキーデータより低く、最小値がこれらのキーデータより高いことを維持し、秩序化された中間データの再配置を回避します.完了すると,配列の中間空席は必然的に空になり,このbufferを配列の中間空席に書き込む.次いで、外部のより小さな部分を再帰的に並べ替え、他の部分を循環的に並べ替える.
三路基数快速列(Three-way Radix Quicksort、Multikey Quicksort、Multi-key Quicksortとも呼ばれる):基数並べ替え(radix sort、例えば一般的な文字列比較並べ替えが基数並べ替えである)と快速並べ替えの特徴を結合し、文字列並べ替えにおける比較的効率的なアルゴリズムである.このアルゴリズムが配列を並べ替える要素には、文字列のようなmultikeyという特徴があり、各アルファベットはkeyと見なすことができる.アルゴリズムは、並べ替えられた配列の中で任意に1つの要素をキーデータとして選択するたびに、まずこの要素の最初のkey(アルファベット)のみを考慮し、その後、他の要素をkeyの比較によってキーデータより小さい、等しい、大きいの3つの部分に分ける.次いで、このkey位置に基づいて「小さい」および「大きい」部分を再帰的にソートし、次のkeyに基づいて「等しい」部分をソートする.
1.分治法設計
2.メモリの節約
3.非常に実用的
アルゴリズムプロセス:
ソートする配列をA[0]......A[N-1]とし、まず任意のデータ(通常は最初のデータ)をキーデータとして選択し、それより小さい数をすべて前に置き、それより大きい数をすべて後ろに置くプロセスを高速シーケンスと呼ぶ.なお、高速ソートは安定したソートアルゴリズムではなく、すなわち、複数の同じ値の相対位置がアルゴリズムの終了時に変動する可能性がある.
1回の高速ソートのアルゴリズムは、次のとおりです.
1)2つの変数I,Jを設定し,ソート開始時:I=0,J=N-1;
2)キーデータとして最初の配列要素を用いてkey,すなわちkey=A[0];
3)Jから前方探索を開始し、すなわち後から前方探索を開始し(J=J-1)、keyより小さい最初の値A[J]を見つけ、keyと交換する.
4)Iから後方探索を開始し、すなわち前から後方探索を開始し(I=I+1)、keyより大きい最初のA[I]を見つけ、keyと交換する.
5)I=Jになるまで、3、4、5のステップを繰り返す.(3,4ステップは、プログラム中に見つからなかったときj=j-1,i=i+1であり、見つかるまで.見つけて交換したときi,jポインタの位置は変わらない.また、i=jの場合、このプロセスはちょうどi+またはj-が完了した最後の別のループが終了するに違いない.)
例えば、ソートされる配列Aの値は、(初期キーデータ:X=49)キーXが永遠に変わらないことに注意し、常にXと比較し、どんな位置でも、最後の目的はXを真ん中に、小さいものを前に大きく後ろに置くことです.
A[0] A[1] A[2] A[3] A[4] A[5] A[6]:
49 38 65 97 76 13 27
初回交換後:27,3865,97,7613 49
(アルゴリズムの3ステップ目に従って後で探します)
2回目の交換後:27,38,49,97,763,65
(アルゴリズムの第4ステップに従って前から>Xの値を探し、65>49、両者を交換し、この場合:I=3)
3回目の交換後:27,38,13,97,765
(アルゴリズムの5ステップ目に従ってアルゴリズムを再び実行する3ステップ目を後で探します
4回目の交換後:27,38,13,49,76,765
(アルゴリズムの第4のステップに従って、前からXより大きい値を探し、97>49、両者を交換し、この場合:I=4、J=6)
このとき第3のステップが実行されるとI=Jとなり、1回の高速ソートが終了すると、1回の高速ソート後の結果は、27,38,13,49,76,9765、すなわち、49より大きいすべての数が49の後にあり、49より小さいすべての数が49の前にある.
へんしゅアルゴリズム
クイックソート(Quicksort)には、いくつかの特筆すべき変種アルゴリズムがあります.ここでは、いくつかの簡単な説明を行います.
ランダム化されたクイック・ソート:クイック・ソートの最悪の状況は、各分割によるプライマリ・エレメントの選択に基づいています.基本的なクイックソートは、最初の要素をマスターとして選択します.これにより,配列が秩序化された場合,分割ごとに最悪の結果が得られる.比較的一般的な最適化方法は、ランダム化アルゴリズム、すなわち、要素をホストとしてランダムに選択することである.この場合,最悪はO(n^2)であるが,最悪は入力データに依存するのではなく,ランダム関数の値取りが悪いためである.実際,ランダム化高速ソートにより理論的最悪の場合が得られる可能性は1/(2^n)にすぎない.従って、ランダム化された高速ソートは、ほとんどの入力データに対してO(nlogn)の所望の時間複雑度に達することができる.ある先輩は「ランダム化された迅速なソートは、一生の人柄のニーズを満たすことができる」と透徹した総括をした.
ランダム化の迅速なソートの唯一の欠点は、入力データに同じデータがたくさんあると、ランダム化の効果が直接弱まることです.限界の場合,すなわちn個の同じ数の並べ替えでは,ランダム化された高速並べ替えの時間的複雑さはO(n^2)に間違いなく低下する.解決策は,交換なしでメタが元の位置に残るように走査する方法である.
バランスエクスプレス(Balanced Quicksort):可能な限り中値を表す要素をキーデータとして選択し、通常のエクスプレスの原則に従って比較、置換、再帰する.通常、このデータを選択する方法は、先頭、末尾、中間の3つのデータを取り、その中の中値を比較して選択することである.この3つの値をとる利点は,実際の問題(例えば情報学コンテスト…)では,近似順序データや逆順序データが出現する確率が高く,このとき中間データは必然的に中値となり,事実上の近似中値でもある.万一、ちょうど中央の大きい2辺の小さい(あるいは逆)データに出会って、取った値はすべて最値に近いならば、少なくとも2つの部分を分けることができるため、実際の効率も2倍ぐらい増加することができて、その上データを少し乱して、退化の構造を破壊するのに有利です.
外部クイックソート(External Quicksort):通常のクイックソートとは異なり、キーデータはbufferであり、まず前と後のM/2要素をbufferに読み込み、そのbufferの要素をソートし、次にソートされた配列の先頭(または末尾)から次の要素を読み込みます.この要素がbufferの最小要素より小さい場合、最初の空席に書きます.この要素がbufferの中で最大の要素より大きい場合、最後の空席に書きます.そうでなければbufferの最大または最小の要素を配列に書き込み、この要素をbufferに配置します.最大値がこれらのキーデータより低く、最小値がこれらのキーデータより高いことを維持し、秩序化された中間データの再配置を回避します.完了すると,配列の中間空席は必然的に空になり,このbufferを配列の中間空席に書き込む.次いで、外部のより小さな部分を再帰的に並べ替え、他の部分を循環的に並べ替える.
三路基数快速列(Three-way Radix Quicksort、Multikey Quicksort、Multi-key Quicksortとも呼ばれる):基数並べ替え(radix sort、例えば一般的な文字列比較並べ替えが基数並べ替えである)と快速並べ替えの特徴を結合し、文字列並べ替えにおける比較的効率的なアルゴリズムである.このアルゴリズムが配列を並べ替える要素には、文字列のようなmultikeyという特徴があり、各アルファベットはkeyと見なすことができる.アルゴリズムは、並べ替えられた配列の中で任意に1つの要素をキーデータとして選択するたびに、まずこの要素の最初のkey(アルファベット)のみを考慮し、その後、他の要素をkeyの比較によってキーデータより小さい、等しい、大きいの3つの部分に分ける.次いで、このkey位置に基づいて「小さい」および「大きい」部分を再帰的にソートし、次のkeyに基づいて「等しい」部分をソートする.
public class QuickSort {
public static void sort(Comparable[] data, int low, int high) {
// ，
int i = low;
int j = high;
if (low < high) {
//
Comparable pivotKey = data[low];
// i,j;i ，j
while (i < j) {
while (i < j && data[j].compareTo(pivotKey) > 0) {
j--;
}// end while
if (i < j) {
//
data[i] = data[j];
i++;
}// end if
while (i < j && data[i].compareTo(pivotKey) < 0) {
i++;
}// end while
if (i < j) {
//
data[j] = data[i];
j--;
}// end if
}// end while
//
data[i] = pivotKey;
//
sort(data, low, i - 1);
//
sort(data, i + 1, high);
}// end if
}// end sort
public static void main(String[] args) {
// JDK1.5 ，
// int,double Comparable
Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 };
sort(c, 0, c.length - 1);
for (Comparable data : c) {
System.out.println(data);
}
}
}