Java のクイックソートアルゴリズム

Java のクイック ソートは、パーティション交換ソートとも呼ばれ、分割統治型のソート アルゴリズムです。クイック ソートは、分割統治の性質により CPU キャッシュを最適に使用するアルゴリズムの良い例です。クイックソート アルゴリズムは、特に大きなリストを並べ替えるために最もよく使用される並べ替えアルゴリズムの 1 つであり、ほとんどのプログラミング言語で実装されています。クイックソート アルゴリズムは、元のデータを 2 つの部分に分割します。個別に並べ替えた後、結合して並べ替えられたデータを生成します。

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

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

配列 {8, 6, 3, 4, 9, 2, 1, 7} をクイック ソートを使用して並べ替える必要があると考えてみましょう。

クイック並べ替えアルゴリズムを実装する手順

1.配列から pivot という要素を選択します。一般に、中央の要素がピボットとして選択されます。 4 を軸にしましょう。

2.ピボットより小さい要素がピボットの前に配置され、ピボットより大きい要素がピボットの後に配置されるように、配列を 2 つの部分に再配置します。次の手順に従います:

• 一番左の要素、つまり 8 を選択します。 4 がピボットであり、8 は 4 より大きいため、8 を 4 の右側に移動する必要があります。右側では、4 より大きいため 7 をそのままにし、8 と交換するために 1 を選択します。したがって、交換後の配列は次のようになります: 1,6,3,4,9,2,8,7
• 左隣の要素、つまり 6 を選択します。 4 がピボットであり、6 は 4 より大きいため、6 を 4 の右側に移動する必要があります。右側では、4 より大きいため 7,8 をそのままにし、6 と交換するために 2 を選択します。したがって、交換後の配列は次のようになります: 1,2,3,4,9,6,8,7
• ピボットの左側にあるすべての要素はピボットより小さく、ピボットの右側にあるすべての要素はピボットより大きいため、ピボットとして 4 を使用する作業は完了です。

3.左側のサブ配列 (ピボットより小さい要素を持つ配列) と右側のサブ配列 (ピボットより大きい要素を持つ配列) にステップ 1 と 2 を再帰的に適用します。配列に要素が 1 つしか含まれていない場合、または要素が含まれていない場合、配列は並べ替えられているとみなされます。

クイックソートアルゴリズムを実装するプログラム

これは、クイック ソート アルゴリズムを使用して整数の配列をソートする Java プログラムです。

コード:

import java.lang.*;
import java.util.*;
public class Main {
private int array[];
private int length;
public void sort(int[] inputArrayArr) {
if (inputArrayArr == null || inputArrayArr.length == 0) {
return;
}
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
}
private void performQuickSort(int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array[lowerIndex+(higherIndex-lowerIndex)/2];
// Divide into two subarrays
while (i <= j) {
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
}
}
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
}
private void swapNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String args[]){
Main quickSort = new Main();
int[] inputArray = {8,6,3,4,9,2,1,7};
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
}
}

出力:

クイックソートアルゴリズムの利点

クイックソートアルゴリズムの利点は次のとおりです:

• 優れた参照局所性: 参照局所性とは、プロセッサが短期間に同じメモリ位置に繰り返しアクセスできる能力です。 Java のクイック ソートは、キャッシュ ミスの数が非常に少ないため、参照の優れた局所性を提供します。これは、最新のアーキテクチャではパフォーマンスにとって重要です。
• クイック ソートは並列化可能: 配列をより小さな領域に分割する最初のステップが完了すると、すべての個々のサブ配列を独立して並列的にソートできます。この理由により、クイック ソートのパフォーマンスが向上します。

クイックソートの複雑さの分析

クイックソートは、分割統治の原則に従って動作する、高速な末尾再帰アルゴリズムです。以下は、最良、平均、最悪のケースにおける複雑さの分析です:

• ベストケースの複雑さ: 配列またはリストに n 個の要素が含まれる場合、最初の実行には O (n) が必要になります。残りの 2 つの部分配列のソートには 2*O (n/2) がかかります。これで、最良の場合の複雑さは O (n logn) になります。
• 平均ケース複雑度: クイックソートの平均ケースは O (n log n) です。
• 最悪の場合の複雑さ: 最初または最後を選択すると、ほぼソートされたデータまたはほぼ逆ソートされたデータのパフォーマンスが最悪の場合になります。クイックソートは最悪の場合 O (n^2) を実行します。

Java では、配列。 Sort () メソッドは、クイック ソート アルゴリズムを使用して配列をソートします。

以上がJava のクイックソートアルゴリズムの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。