Java でのクイックソート-＆＃＆チュートリアル-php.cn

Java でのクイックソート

王林

リリース： 2024-08-30 15:32:02

オリジナル

914 人が閲覧しました

次の記事「Java のクイックソート」では、Java のクイックソートアルゴリズムの概要を説明します。クイックソートアルゴリズムは、マージソートアルゴリズムと似た効率的なソートアルゴリズムの 1 つです。これは、リアルタイムの並べ替え目的で広く使用されているアルゴリズムの 1 つです。このアルゴリズムの最悪の場合の時間計算量は O(n^2)、平均的な場合の時間計算量は O(n log n)、最良の場合の時間計算量は O(n log n) です。

O(n log n) の場合の空間計算量。n は入力のサイズです。ソートのプロセスには、入力の分割、再帰的反復、および再帰ごとに重要な要素のマーク付けが含まれます。このアルゴリズムの並べ替えの種類には、反復的な方法での隣接する要素の比較が含まれます。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェアテスト、その他

Java でのクイックソートはどのように機能しますか?

Quick Sort アルゴリズムは、効率的な方法で設計され実行される一連のステップを含む疑似コードを形成することで Java に実装できます。

クイックソートアルゴリズムが機能する主な原理は、分割統治アプローチに基づいており、効率的なソートアルゴリズムでもあります。
入力配列はサブ配列に分割され、分割は中心要素であるピボット要素に基づいて行われます。ピボット要素の両側のサブ配列は、実際に並べ替えが行われる主な領域です。
中央のピボット要素は、配列を 2 つのパーティションに分割するためのベースであり、配列要素の左半分はピボット要素より小さく、配列要素の右半分はピボット要素より大きくなります。
ピボット要素について考える前に、配列の要素の中から任意の要素をピボット要素にすることができます。これは通常、理解を容易にするために、中央のもの、最初のもの、または最後のものとみなされます。ピボット要素は、配列要素のいずれかからランダムに選択できます。
この例では、配列の最後の要素がピボット要素とみなされ、サブ配列の分割は配列の右端から始まります。
最後に、並べ替えプロセスの完了後にピボット要素が実際に並べ替えられた位置になります。並べ替えの主なプロセスは並べ替えアルゴリズムのパーティションロジックにあります。
アルゴリズムの効率は、サブ配列のサイズとそれらのバランスがどのように保たれているかによって異なります。サブ配列のバランスが崩れると、時間の計算量が増加し、最悪の場合の計算量が増加します。
特定の開始、終了、または中間のインデックスをピボット要素として選択する代わりに、ランダムな方法でピボット要素を選択すると、多くの場合、最良の時間計算量が得られます。

Java でのクイックソートの実装例

QuickSort アルゴリズムは以下のように Java プログラミング言語を使用して実装されており、出力コードはコードの下に表示されます。

コードは最初に、配列、初期インデックス、最終インデックス、つまり配列の長さを引数として、quickSortAlgo() メソッドを使用して入力を受け取ります。
quickSortAlgo() メソッドを呼び出した後、初期インデックスが最終インデックスより小さいかどうかを確認し、arrayPartition() メソッドを呼び出してピボット要素の値を取得します。
パーティション要素には、ピボット要素の周囲の要素値に基づいて小さい要素と大きい要素を配置するロジックが含まれています。
パーティションメソッドの実行後にピボット要素のインデックスを取得した後、すべてのサブ配列が完全にパーティション化され並べ替えられるまで、quickSortAlgo() メソッドが単独で再帰的に呼び出されます。
パーティションロジックでは、最後の要素がピボット要素として割り当てられ、最初の要素がピボット要素と比較されます。つまり、要素が小さいか大きいかに基づいて交換される最後の要素です。
この再帰プロセスは、配列のすべての要素が分割されて並べ替えられるまで行われ、最終結果は結合された並べ替えられた配列になります。
要素がピボット要素以下の場合にのみ、for ループ反復内で要素が交換されます。
反復プロセスが完了すると、最後の要素が交換されます。つまり、ピボット要素の値が左側に移動されて、新しいパーティションが作成され、同じプロセスが再帰の形で繰り返され、その結果、一連の結果が得られます。指定された配列要素からのサブ配列の形成として、考えられるさまざまなパーティションに対するソート操作。
以下のコードはどの IDE でも実行でき、main() の配列値を変更することで出力を確認できます。 main メソッドは、コンソールに出力を取得する目的のみに使用されます。 Javaコーディング標準の一環として、以下のmainメソッドを削除してオブジェクトを作成し、非静的メソッドにして呼び出すことが可能です。

Java でのクイックソートアルゴリズムのコード実装

以下はコード実装です:

コード:

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm {
public static void main(String[] args) {
int[] array = { 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 };
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) {
System.out.print(ar + " ");
}
}
public static int arrayPartition(int[] array, int start, int end) {
int pivot = array[end];
int i = (start - 1);
for (int ele = start; ele < end; ele++) {
if (array[ele] <= pivot) {
i++;
int swap = array[i];
array[i] = array[ele];
array[ele] = swap;
}
}
// Swapping the elements
int swap = array[i + 1];
array[i + 1] = array[end];
array[end] = swap;
return i + 1;
}
public static void quickSortAlgo(int[] arrayTobeSorted, int start, int end) {
if (start < end) {
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
}
}
}

ログイン後にコピー

出力:

Java でのクイックソート