はじめに
クイックソートは、分割統治法に基づくソートアルゴリズムです。このアルゴリズムは、配列から「ピボット」要素を選択し、その他の要素をピボットよりも小さいか大きいかに応じて 2 つのサブ配列に分割することで動作します。その後、サブ配列を再帰的にソートします。クイックソートの平均的な計算量は O(n log n) です。なお、クイックソートは安定ソートではなく、つまり、等しいソート項目の相対的な位置が保たれない場合があります。
効率的なクイックソート分割統治法アルゴリズム
💡 このチュートリアルは英語版からAIによって翻訳されています。原文を確認するには、 ここをクリックしてください
Arrays クラスをインポートする
このステップでは、java.util.Arraysクラスをインポートする必要があります。このクラスには、int配列をStringに変換するために使用される、配列を操作するいくつかのメソッドが含まれています。
import java.util.Arrays;partition() メソッドを定義する
partition()という名前のヘルパーメソッドを定義します。partition()メソッドは、配列arr、開始インデックスlow、および終了インデックスhighを入力として受け取ります。partition()メソッドは、要素を 1 つピボットとして選択し、その要素より小さいすべての要素がピボットの左に、そしてピボットより大きいすべての要素がピボットの右になるように要素を分割します。ピボット要素は、その正しい位置に配置されます。
partition()メソッドは、分割された要素のインデックスを返します。分割された要素は、ピボット要素が配置される位置です。
public static int partition(int[] arr, int low, int high) {
// ピボット要素を選択する
int pivot = arr[high];
int i = (low - 1); // より小さい要素のインデックスで、これまで見つけたピボットの右の位置を示す
for (int j = low; j <= high - 1; j++) {
// 現在の要素がピボット以下の場合
if (arr[j] <= pivot) {
i++; // より小さい要素のインデックスをインクリメントする
// arr[i] と arr[j] を交換する
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// arr[i + 1] と arr[high] を交換する
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 分割インデックスを返す
}ブラウザでそのまま実践！
quicksort() メソッドを定義する
quicksort()という名前のソートメソッドを定義します。quicksort()メソッドは、配列arr、開始インデックスlow、および終了インデックスhighを入力として受け取ります。quicksort()メソッドは、再帰的にarr[]配列をソートします。
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi は分割インデックスで、arr[p] は今
// 正しい位置にあります
int pi = partition(arr, low, high);
// 分割の前と分割の後の要素を再帰的にソートする
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}整数配列を作成して割り当てる
ソートするための整数配列を作成し、arrフィールドに割り当てます。
int[] arr = {7, 9, 1, 2, 10, 15, 6};学びながらコードを書こう。
クイックソートを実装する
arrフィールドを入力として、配列の最初と最後のインデックスとともにquickSort()メソッドを呼び出します。Arrays.toString(arr)メソッドを使用して配列をソートして表示します。
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));複数の配列でテストする
さまざまな特性を持つ配列を使って、あなたのクイックソートの実装をテストします。
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));ピボットをランダムに選択する
このステップでは、最悪ケースを回避するため、各反復でピボットをランダムに選択する必要があります。これを達成するには、partition() メソッドを更新して、次の行を置き換えます。
int pivot = arr[high];この行に置き換えます。
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;ランダム化されたピボット要素を使ってテストする
ランダム化されたピボット要素を使って、あなたのクイックソートの実装をテストします。
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));端数ケースを処理する
このステップでは、クイックソートが処理できる端数ケースについて説明します。これらの端数ケースを整数配列として定義します。
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));完成コード
Java の実験でのクイックソートの完成コードを以下に示します。
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}まとめ
この実験では、Java でクイックソートアルゴリズムを実装するための手順を段階的に示しました。ピボット選択はクイックソートにおいて重要なステップであり、異なるピボット選択手法がアルゴリズムの性能に影響を与えることがわかりました。クイックソートは大量のデータをソートする際に最適です。クイックソートの最悪ケースの時間計算量は O(N^2) ですが、平均および最良ケースの時間計算量は O(NLogN) です。
