quicksort java algorithm
このチュートリアルでは、コード例を使用して、Javaでのクイックソートアルゴリズム、その図、JavaでのQuickSortの実装について説明します。
クイックソートソート技術は、ソフトウェアアプリケーションで広く使用されています。クイックソートは、マージソートのような分割統治戦略を使用します。
クイックソートアルゴリズムでは、「ピボット」と呼ばれる特別な要素が最初に選択され、問題の配列またはリストが2つのサブセットに分割されます。パーティション化されたサブセットは、サイズが等しい場合と等しくない場合があります。
=> EasyJavaトレーニングシリーズをお読みください。
c ++インタビューの質問と回答pdf
パーティションは、ピボット要素よりも小さい要素はすべてピボットの左側にあり、ピボットよりも大きい要素はピボットの右側にあるようになっています。クイックソートルーチンは、2つのサブリストを再帰的にソートします。クイックソートは、大きな配列やリストでも効率的かつ高速に動作します。
学習内容：
クイックソートパーティションJava
パーティショニングは、クイックソート手法の重要なプロセスです。では、パーティショニングとは何ですか？
配列Aが与えられた場合、xより小さいすべての要素がxの前にあり、xより大きいすべての要素がxの後にあるように、ピボットと呼ばれる値xを選択します。
ピボット値は次のいずれかになります。
- 配列の最初の要素
- 配列の最後の要素
- 配列の中央要素
- 配列内の任意のランダム要素
次に、このピボット値は、配列を分割することにより、配列内の適切な位置に配置されます。したがって、「パーティショニング」プロセスの出力は、適切な位置でのピボット値と、左側のピボットよりも小さい要素、および右側のピボットよりも大きい要素です。
パーティショニングプロセスを説明する次の図を検討してください。
上の図は、配列の最後の要素をピボットとして繰り返し選択することにより、配列を分割するプロセスを示しています。各レベルで、ピボットを正しい位置に配置することにより、配列を2つのサブ配列に分割することに注意してください。
次に、パーティションルーチンも含むクイックソート手法のアルゴリズムと擬似コードをリストします。
c ++マージソートアルゴリズム
クイックソートアルゴリズムJava
クイックソートの一般的なアルゴリズムを以下に示します。
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low 以下に、クイックソート手法の擬似コードを示します。
クイックソート用の擬似コード
以下は、クイックソートソート手法の擬似コードです。クイックソートとパーティショニングルーチン用の擬似コードを提供していることに注意してください。
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low 図
クイックソートアルゴリズムの図を見てみましょう。例として次の配列を取り上げます。ここでは、最後の要素をピボットとして選択しました。
示されているように、最初の要素には低のラベルが付けられ、最後の要素には高のラベルが付けられています。
上の図で明らかなように、配列の最後の要素と最初の要素をそれぞれ指す、highとlowの2つのポインターがあります。クイックソートが進むにつれて、これらのポインターは両方とも移動します。
ローポインタが指す要素がピボット要素より大きくなり、ハイポインタが指す要素がピボット要素より小さくなると、ローポインタとハイポインタが指す要素を交換し、各ポインタが1位置進みます。
上記の手順は、配列内で両方のポインターが互いに交差するまで実行されます。それらが交差すると、ピボット要素は配列内の適切な位置になります。この時点で、配列はパーティション化されており、クイックソートアルゴリズムを各サブ配列に再帰的に適用することで、各サブ配列を個別にソートできます。
Javaでのクイックソートの実装
クイックソート手法は、再帰または反復のいずれかを使用してJavaで実装できます。このセクションでは、これらのテクニックの両方を見ていきます。
再帰的クイックソート
上に示したクイックソートの基本的な手法では、配列のソートに再帰を使用していることがわかっています。配列を分割した後の再帰的クイックソートでは、クイックソートルーチンが再帰的に呼び出され、サブ配列がソートされます。
以下の実装は、再帰を使用したクイックソート手法を示しています。
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j 出力：
元の配列：(4、-1、6、8、0、5、-3)
ソートされた配列：(-3、-1、0、4、5、6、8)
反復クイックソート
反復クイックソートでは、再帰とソートパーティションを使用する代わりに、補助スタックを使用して中間パラメーターを配置します。
次のJavaプログラムは、反復クイックソートを実装しています。
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 出力：
元の配列：(3、2、6、-1、9、1、-6、10、5)
ソートされた配列：(-6、-1、1、2、3、6、9、10、5)
よくある質問
Q＃1）クイックソートはどのように機能しますか？
回答： クイックソートは分割を使用し、戦略を征服します。クイックソートは最初に、選択されたピボット要素の周りに配列を分割し、再帰的にソートされるサブ配列を生成します。
Q＃2）クイックソートの時間計算量はどれくらいですか？
回答： クイックソートの平均時間計算量はO（nlogn）です。最悪の場合、選択ソートと同じO（n ^ 2）です。
Q＃3）クイックソートはどこで使用されますか？
選択ソートアルゴリズムc ++
回答： クイックソートは主に再帰的なアプリケーションで使用されます。クイックソートはCライブラリの一部です。また、組み込みのソートを使用するほとんどのプログラミング言語は、クイックソートを実装しています。
Q＃4）クイックソートの利点は何ですか？
回答：
- クイックソートは効率的なアルゴリズムであり、要素の膨大なリストでも簡単に並べ替えることができます。
- インプレースソートであるため、余分なスペースやメモリは必要ありません。
- これは広く使用されており、任意の長さのデータセットを並べ替える効率的な方法を提供します。
Q＃5）クイックソートがマージソートよりも優れているのはなぜですか？
回答： クイックソートがマージソートよりも優れている主な理由は、クイックソートがインプレースソート方式であり、追加のメモリスペースを必要としないことです。マージソートでは、中間ソート用に追加のメモリが必要です。
結論
クイックソートは、主にO（nlogn）時間で巨大なデータセットをソートする効率があるため、最良のソートアルゴリズムと見なされています。
クイックソートもインプレースソートであり、追加のメモリスペースを必要としません。このチュートリアルでは、クイックソートの再帰的かつ反復的な実装を見てきました。
次のチュートリアルでは、Javaでのソート方法を続行します。
推奨読書
