Javaでのクイックソートアルゴリズムの実装
1概要
このチュートリアルでは、Javaの実装に焦点を当てて、QuickSortアルゴリズムを詳しく調べます。
また、その長所と短所について説明し、次に時間の複雑さを分析します。
2クイックソートアルゴリズム
-
クイックソートは、分割統治の原則を利用しているソートアルゴリズムです。
** 平均的な
O（n log n）
複雑さを持ち、特に大量のデータを扱う場合に最も使用されるソートアルゴリズムの1つです。 -
Quicksortは安定したアルゴリズムではないことを忘れないでください。
** 安定ソートアルゴリズムは、入力リストに表示されるのと同じ値を持つ要素がソートされた出力に同じ順序で表示されるアルゴリズムです。
入力リストは、pivotという要素によって2つのサブリストに分けられます。ピボットより小さい要素を持つサブリストと、ピボットより大きい要素を持つサブリストです。このプロセスはサブリストごとに繰り返されます。
最後に、ソートされたすべてのサブリストがマージされて最終的な出力が形成されます。
** 2.1. アルゴリズムステップ
-
リストからピボットと呼ばれる要素を選択します. 私たちはそれを使用します
リストを2つのサブリストに分割します。
-
ピボットの周りのすべての要素を並べ替えます.
値はその前に配置され、それ以降のすべての要素はピボットより大きくなります。このステップの後、ピボットはその最終位置にあります。これは重要なパーティションステップです。
-
上記の手順を左側のサブリストと両方のサブリストに再帰的に適用します.
ピボットの右
ご覧のとおり、** クイックソートは、すべての分割統治アプローチと同様に、当然再帰的なアルゴリズムです。
このアルゴリズムをよりよく理解するために簡単な例を見てみましょう。
Arr[]= {5, 9, 4, 6, 5, 3}-
簡単にするために、ピボットとして5を選択したとしましょう.
-
最初に5未満のすべての要素を最初の位置に配置します.
配列:\ {3、4、5、6、5、9}
。それから、左の部分配列\ {3,4}に対してそれを繰り返します。
ピボット
。 3未満の要素はありません
-
ピボットの右側のサブアレイにクイックソートを適用します.
\ {4}
。このサブ配列は1つのソート済み要素のみで構成されています
-
元の配列の正しい部分、\ {6、5、9}を続けます.
最後の順序付き配列を取得するまで
2.2. 最適なピボット
を選択する
QuickSortの重要なポイントは、最適なピボットを選択することです。真ん中の要素は、リストを2つの等しいサブリストに分割するので、もちろん最善です。
しかし、番号なしリストから中央の要素を見つけるのは困難で時間がかかるため、最初の要素、最後の要素、中央値、またはその他のランダム要素をピボットとして使用します。
** 3 Javaでの実装
最初のメソッドは
quickSort（）
で、ソート対象の配列、最初と最後のインデックスをパラメータとして取ります。まず、インデックスを確認し、ソートする要素がまだある場合にのみ続行します。
ソートされたピボットのインデックスを取得し、それを使用して、
quickSort（）
メソッドと同じパラメータを使用して
partition（）
メソッドを再帰的に呼び出しますが、インデックスは異なります。
public void quickSort(int arr[], int begin, int end) {
if (begin < end) {
int partitionIndex = partition(arr, begin, end);
quickSort(arr, begin, partitionIndex-1);
quickSort(arr, partitionIndex+1, end);
}
}
partition（）
メソッドを続けましょう。簡単にするために、この関数は最後の要素をピボットとして取ります。次に、各要素を確認し、その値が小さい場合はピボットの前に要素を交換します。
分割の終わりまでに、ピボットよりも小さいすべての要素はその左側にあり、ピボットより大きいすべての要素はその右側にあります。ピボットはその最終的なソート位置にあり、関数はこの位置を返します。
private int partition(int arr[], int begin, int end) {
int pivot = arr[end];
int i = (begin-1);
for (int j = begin; j < end; j++) {
if (arr[j]<= pivot) {
i++;
int swapTemp = arr[i];
arr[i]= arr[j];
arr[j]= swapTemp;
}
}
int swapTemp = arr[i+1];
arr[i+1]= arr[end];
arr[end]= swapTemp;
return i+1;
}
4アルゴリズム解析
4.1. 時間の複雑さ
最良の場合、アルゴリズムはリストを2つの等しいサイズのサブリストに分割します。したがって、フル
n
サイズのリストの最初の反復には
O（n）
が必要です。残りの2つのサブリストを
n/2
個の要素でソートすると、それぞれ
2 ** O（n/2）
になります。結果として、QuickSortアルゴリズムは
O（n log n）
という複雑さを持ちます。
最悪の場合、アルゴリズムは各反復で1つの要素のみを選択するため、
O（n）O（n-1）… O（1）
は
O（n ^ 2 ^）
と等しくなります。
QuickSortは平均して
O（n log n）
の複雑さを持つため、大容量のデータに適しています。
4.2. QuickSortとMergeSort
どの場合にMergeSortよりもQuickSortを選択すべきかについて説明しましょう。
QuicksortとMergesortはどちらも
O（n log n）
の平均時間複雑度を持っていますが、
O（log（n））
スペース複雑さを持っているのでQuicksortは好ましいアルゴリズムです。一方、Mergesortは
O（n）
追加の記憶域を必要とするため、配列に対して非常に高価になります。
クイックソートでは、操作のためにさまざまなインデックスにアクセスする必要がありますが、連続するブロックがないため、このアクセスはリンクリストでは直接実行できません。したがって、要素にアクセスするには、リンクリストの先頭から各ノードを反復する必要があります。また、Mergesortは__LinkedListsのための余分なスペースなしで実装されています。
そのような場合、QuicksortとMergesortのオーバーヘッドの増加が一般的には好まれます。
5結論
クイックソートはエレガントなソートアルゴリズムで、ほとんどの場合非常に便利です。
-
これは一般的に「インプレース」アルゴリズムであり、平均時間の複雑さは__O（n log n）です。
言及するもう一つの興味深い点は、Javaの
Arrays.sort（）
メソッドがプリミティブの配列をソートするためにQuicksortを使うということです。この実装は2つの要点を使用しており、単純なソリューションよりもはるかに優れたパフォーマンスを発揮します。そのため、プロダクションコードでは通常ライブラリメソッドを使用するほうが優れています。
いつものように、このアルゴリズムを実装するためのコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[私たちのGitHubレポジトリ]にあります。