双方向クイックソート

双方向クイックソートはランダム化クイックソートの改良版であり、partition プロセスでは2つのインデックス値（i、j）を使って配列を走査し、<vの要素をインデックスiが指す位置の左側に置き、>vの要素をインデックスjが指す位置の右側に置き、vはピボット値を表します。

適用説明

時間・空間計算量はランダム化クイックソートと同じです。重複要素が多数ある配列では、前節のランダム化クイックソートを使うと効率が非常に低く、partition 後にピボットより大きいデータまたは小さいデータのサブ配列の長さが極端に不均衡になり、最終的にはO(n*2)時間計算量のアルゴリズムに退化してしまいます。このような場合は、双方向クイックソートアルゴリズムを使用できます。

プロセス図

2つのインデックス値（i、j）を使用してシーケンスを走査し、<=vの要素をインデックス i が指す位置の左側に置き、>=vの要素をインデックス j が指す位置の右側に置き、左右のサブ配列のバランスを取ります。

Java サンプルコード

ソースコードパッケージのダウンロード：Download

QuickSort2Ways.java ファイルコード：

package サンプル;

/**
* 双方向クイックソート
*/
public class QuickSort2Ways {

//核心コード---開始
private static int partition(Comparable[] arr, int l, int r){
// arr[l...r] の範囲からランダムに1つの値をピボットとして選択する
swap( arr, l , (int)(Math.random()*(r-l+1))+l );
Comparable v = arr[l];
// arr[l+1...i) <= v; arr(j...r] >= v
int i = l+1, j = r;
while( true ){
while( i <= r && arr[i].compareTo(v) < 0 )
i ++;
while( j >= l+1 && arr[j].compareTo(v) > 0 )
j --;
if( i > j )
break;
swap( arr, i, j );
i ++;
j --;
}
swap(arr, l, j);
return j;
}
//核心コード---終了

// 再帰的にクイックソートを使用し、arr[l...r] の範囲をソートする
private static void sort(Comparable[] arr, int l, int r){
if (l >= r) {
return;
}
int p = partition(arr, l, r);
sort(arr, l, p-1 );
sort(arr, p+1, r);
}

public static void sort(Comparable[] arr){

int n = arr.length;
sort(arr, 0, n-1);
}

private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}

// QuickSort をテストする
public static void main(String[] args) {

// 双方向クイックソートも O(nlogn) の時間計算量を持つアルゴリズムである
// 100万件規模のデータを1秒以内で余裕を持って処理できる

// Quick Sort も O(nlogn) の時間計算量を持つアルゴリズムである
// 100万件規模のデータを1秒以内で余裕を持って処理できる
int N = 1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
sort(arr);
SortTestHelper.printArray(arr);

}
}

アルゴリズム原理の詳解

双方向クイックソートの核心は、その双方向ポインタによるパーティション方法。単方向クイックソート（片端からのみ走査する）とは異なり、2つのポインタを使用し、ソート対象のサブ配列の先頭と末尾からそれぞれ中央に向かって走査することで、等しい要素がすべて片側に寄せられることを防ぎます。

核心：双方向パーティション処理

配列arr内のインデックスleft 到 rightの部分をソートするとします。

ピボットの選択：arr[left...right]の中からランダムに1つの要素をピボットとして選択しますpivot。ランダム化は、整列済み配列で最悪のケースが発生するのを防ぐためです。

ポインタの初期化：

i = left + 1：左から右へ走査するポインタで、最初の以上 pivotの要素を探します。
j = right：右から左へ走査するポインタで、最初の以下 pivotの要素を探します。

走査と交換のループ：

whileループの条件はi <= j。
内側のwhileループ：iを右へ移動し続け、arr[i] >= pivot。
ループ：whileを左へ移動し続け、jこのとき、arr[j] <= pivot。
は左半分にあるべきでない「大きい」要素であり、arr[i]は右半分にあるべきでない「小さい」要素です。arr[j]もしこのとき
ならば交換しますi <= j、その後arr[i]とarr[j]を進め、外側のループを続けます。i++, j--ピボットの配置と分割点の返却

ループ終了後、：

は交差しています（iとj）。このときj < i（つまりピボット）を正しい位置に配置する必要があります。arr[left]交換します。なぜなら
将 arr[left]とarr[j]が最終的に停止した位置の指す要素は、jピボット以下である最後の要素です。を返します
を新しい分割点とします。このとき、j、かつarr[left...j-1] <= pivot，arr[j+1...right] >= pivot再帰ソートarr[j] == pivot。

再帰ソート

を得た後、左のサブ配列pと右のサブ配列arr[left...p-1]に対して再帰的に上記の処理を実行し、サブ配列の長さが1になるまで続けます。arr[p+1...right]コード実装

コード実装

1. メインソート関数

サンプル

public class TwoWayQuickSort {

// 境界条件の処理：配列が空または要素が1つだけの場合はソート不要
public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return; // 再帰的クイックソート関数を呼び出す
}
quickSort(arr, 0, arr.length - 1); // 再帰的クイックソート関数
}

// 再帰終了条件：左端が右端以上の場合、サブ配列はソート済みまたは空
private static void quickSort(int[] arr, int left, int right) {
// 重要なステップ：双方向パーティションを実行し、分割点のインデックスを返す
if (left >= right) {
return;
}

// 左半分 (left, p-1) を再帰的にソートする
int p = partition(arr, left, right);

// 右半分 (p+1, right) を再帰的にソートする
quickSort(arr, left, p - 1);
2. 核心：双方向パーティション関数
quickSort(arr, p + 1, right);
}
}

2. 核心：双方向パーティション関数

サンプル

// 1. ピボットをランダムに選択し、left の位置に交換して、整列済み配列での最悪ケースを回避する
private static int partition(int[] arr, int left, int right) {
// ピボット
int randomIndex = left + (int)(Math.random() * (right - left + 1));
swap(arr, left, randomIndex);
int pivot = arr[left]; // 2. 双方向ポインタを初期化する

// i: 左から右へ走査し、>= pivot の要素を探す
// j: 右から左へ走査し、<= pivot の要素を探す
// 3. メインループ：i と j がまだ交差していない間
int i = left + 1;
int j = right;

// 3.1 左ポインタ i を移動：最初の >= pivot の要素を見つける
while (i <= j) {
// 境界 i <= right に注意し、配列の範囲外アクセスを防ぐ
// 3.2 右ポインタ j を移動：最初の <= pivot の要素を見つける
while (i <= right && arr[i] < pivot) {
i++;
}
// 境界 j >= left+1 に注意。left の位置は pivot 自身だから
// 3.3 ポインタの状態を確認する
while (j >= left + 1 && arr[j] > pivot) {
j--;
}

// i > j の場合、走査は完了して左右のパーティションが整っているため、交換は不要
// 3.4 arr[i] と arr[j] を交換する
if (i > j) {
break;
}

// このとき arr[i] >= pivot, arr[j] <= pivot なので、交換することで大小の要素がそれぞれの位置に収まる
// 交換後、ポインタを移動して走査を続ける
swap(arr, i, j);
// 4. ピボットを最終的な正しい位置 j に配置する
i++;
j--;
}

// ループ終了後、j は最後の <= pivot の要素を指す
// 5. 分割点のインデックス j を返す
swap(arr, left, j);

// 補助関数：配列内の2つの要素の位置を交換する
return j;
}

3. テストと検証
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

3. テストと検証

サンプル

public class Main {
public static void main(String[] args) {
"ソート前: "
int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
System.out.println("ソート後: " + Arrays.toString(arr1));
TwoWayQuickSort.sort(arr1);
System.out.println(// テストケース2：ランダムに生成した大きな配列 + Arrays.toString(arr1));

// 0〜49 の乱数を生成するため、重複の可能性が高い
int[] arr2 = new int[20];
Random rand = new Random();
for (int i = 0; i < arr2.length; i++) {
arr2[i] = rand.nextInt(50); "ランダム配列ソート前: "
}
System.out.println("\n"ランダム配列ソート後: " + Arrays.toString(arr2));
TwoWayQuickSort.sort(arr2);
System.out.println(// ソート結果が正しいかどうかを検証する + Arrays.toString(arr2));

"ソートエラー！"
for (int i = 1; i < arr2.length; i++) {
if (arr2[i] < arr2[i-1]) {
System.out.println("ソート結果の検証に成功しました！");
return;
}
}
System.out.println(テストデータ出力例);
}
}

アルゴリズムの分析と比較：

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过！

アルゴリズムの分析と比較

時間計算量

：$O(n \log n)$。双方向クイックソートは重複要素をバランスよく分散させることで、再帰ツリーが比較的均衡のとれたものになります。最悪の場合
：$O(n^2)$。ランダムにピボットを選択することで確率は大幅に下がりますが、毎回のパーティションが極端に不均衡な場合（例えば、毎回のピボットがその時点での最小値または最大値である場合）には、依然として最悪のケースが発生します。最良の場合
最好情况：$O(n \log n)$。毎回の分割で配列を均等に分割できる。

空間計算量

主に再帰呼び出しスタックが占める空間です。
平均の深さは $O(\log n)$、最悪の場合の深さは $O(n)$ です。
したがって、平均空間計算量は $O(\log n)$、最悪では $O(n)$ です。。

安定性

クイックソート（双方向クイックソートを含む）は安定なソートアルゴリズムではありません。分割の過程で、隣接しない要素の交換が等しい要素の元の相対順序を乱すためです。

単方向・双方向・三方向クイックソートの比較

特性	単方向クイックソート (Lomuto)	双方向クイックソート	三方向クイックソート
分割方式	単一ポインタで左から右へ走査	双方向ポインタで両端から中央へ走査	三つのポインタで、配列を`<pivot`, `=pivot`, `>pivot`三つの部分に分ける
重複要素の処理	悪い、不均衡な分割を引き起こす可能性がある	良い、重複要素をバランスよく分散できる	最適、基準値に等しいすべての要素を一度に処理できる
コードの複雑さ	簡単	中程度	やや複雑
適用シナリオ	教育用、重複要素なし/少ない	汎用的で、特に重複要素がある可能性のあるシナリオに適している	大量の重複要素が存在するシナリオ

その他のコード表示

その他の拡張

ソートアルゴリズム

ヒープ

二分探索木

Union-Find

グラフ理論

双方向クイックソート

適用説明

プロセス図

Java サンプルコード

QuickSort2Ways.java ファイルコード：

アルゴリズム原理の詳解

核心：双方向パーティション処理

再帰ソート

コード実装

1. メインソート関数

サンプル

2. 核心：双方向パーティション関数

サンプル

3. テストと検証

サンプル

アルゴリズムの分析と比較

時間計算量

空間計算量

安定性

単方向・双方向・三方向クイックソートの比較

その他のコード表示