🎯

【Java】クイックソート

2024/03/19に公開

Java

初心者

tech

クイックソートとは

ピボットの選択・比較と分割・再帰という3ステップ踏むを効率的なアルゴリズムです。
ピボットの選択は、基準値であるピボットを選択することです。先頭の要素や中央の要素だったり、ランダムに選んだ要素をピボットに選択したりします。今回は最後の要素をピボットとします。
比較と分割
選択したピボットを基準に、配列内の要素をピボットより小さいものと大きいものに分割します。小さい要素はピボットの左側に、大きい要素は右側に移動させます。
再帰
分割された部分配列に対して再帰的に同じ手順を適用します。各部分配列は独立してソートされ、再帰が終了すると全体の配列がソートされます。

問題の内容

問題
サイズnの数列aをクイックソートせよ。
入力値
```
n = 8
a = 3 5 8 1 7 6 2 4
```

クイックソートの図解

クイックソートを図解すると、下記の通りになります。

本問のクイックソートのコード例

import java.util.*;

public class Main {

    static int count = 0;

    static void quickSort(int[] a, int left, int right) {
        // 再帰処理の終了条件を配列の先頭のインデックス=left が配列の最後のインデックス=right-1 以上に設定
        // →分割した配列の要素数が1個以下になったら再帰終了
        if (left >= right - 1) {
            return;
        }
        // pivot に 配列の最後の要素=a[right-1] を代入
        int pivot = a[right - 1];
        // pivotIndex を 配列の先頭のインデックス=left で初期化
        int pivotIndex = left;
        for (int i = left; i < right - 1; i++) {
            // もし a[i] が pivot より小さいなら
            if (a[i] < pivot) {
                // a[pivotIndex] と a[i] を交換
                int temp = a[pivotIndex];
                a[pivotIndex] = a[i];
                a[i] = temp;
                // pivotIndex を 1 だけ増やす
                pivotIndex++;
                count++;
            }
        }

        // ピボットと a[pivotIndex] を交換
        a[right - 1] = a[pivotIndex];
        a[pivotIndex] = pivot;

        // quickSort(a, left, pivotIndex) を呼び出す
        quickSort(a, left, pivotIndex);
        // quickSort(a, pivotIndex+1, right) を呼び出す
        quickSort(a, pivotIndex+1, right);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        quickSort(a, 0, n);

        for (int i = 0; i < n; i++) {
            if (i > 0) {
                System.out.print(" ");
            }
            System.out.print(a[i]);
        }
        System.out.println();

        System.out.println(count);
    }
}

コード例の解説

本問でも再帰処理を使います。従前に解説したマージソートと同様に、再帰処理は、制御変数の変化を考えて処理の流れを直接追うことが難しいです。
基本的には、上記の 【図解】 と コードの【コメント】 を参考にしてください。
しかし、上記のコード例では、 変数pivotIndex の役割を理解することが、クイックソートの理解にもつながりますので、 変数pivotIndex について解説します。

変数`pivotIndex`の解説

初期化
```
int pivotIndex = left;
```
変数pivotIndexは、配列の左端のインデックスに設定します。

ピボットより小さい要素の移動と pivotIndex の更新
```
for (int i = left; i < right - 1; i++) {
    if (a[i] < pivot) {
        int temp = a[pivotIndex];
        a[pivotIndex] = a[i];
        a[i] = temp;
        pivotIndex++;
        count++;
    }
}
```
1. 配列の左端=leftから右端=right - 1までループするfor文を定義して、
2. 配列の要素a[i]がpivotより小さい場合、
3. 配列の要素a[pivotIndex]とa[i]の位置を交換し、
4. 変数pivotIndexを1増やして、更新します。

ピボットの適切な位置への移動
```
a[right - 1] = a[pivotIndex];
a[pivotIndex] = pivot;
```
1. 配列の右端=ピボットの位置にa[pivotIndex]を移動させて、
2. a[pivotIndex]の位置にピボットを移動させます。

再帰的な呼び出しのための部分配列の境界指定
```
quickSort(a, left, pivotIndex);
quickSort(a, pivotIndex+1, right);
```
1. 再帰的にインデックスのleftからpivotIndexまでを左側の部分配列=ピボット未満の部分配列に指定します。
2. 再帰的にインデックスのpivotIndex+1からrightまでを右側の部分配列=ピボット超過の部分配列に指定します。