クイックソート復習

いつも忘れる
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class QuickSort {
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int partition(int[] arr, int l, int r) {
        // l <= x < r
        int n = r - l;
        // 3 4 7 5 2 8 9 6
        // l               r
        Random random = new Random(System.nanoTime());
        int pivot = random.nextInt(n) + l;
        // 3 4 7 5 2 8 9 6
        // l     ^         r
        swap(arr, pivot, r - 1); // move to right
        // 3 4 7 6 2 8 9 5
        // l             ^ r

        // 3 4 7 6 2 8 9 5
        // ^ ... t
        // 3 4 7 6 2 8 9 5
        //   ^
        // 3 4 7 6 2 8 9 5
        //     ^
        // 3 4 2 6 7 8 9 5
        //       ^
        int t = l;
        for (int i = l; i < r - 1; i++) {
            if (arr[i] <= arr[r - 1]) {
                if (i != t) {
                    swap(arr, i, t);
                }
                t++;
            }
        }
        // 3 4 2 5 7 8 9 6
        //       ^
        swap(arr, r - 1, t);

        return t + 1; // pivot値以上となる部分配列の左端
    }

    public static void qsort(int[] arr, int l, int r) {
        // ↓を出力するとわかりやすい
        // System.out.println(l + "<= x <" + r + " in " + Arrays.toString(arr));

        // l <= x < r
        if (r - l <= 1) return; // 要素数が1以下の場合はソート済みなので終了
        int index = partition(arr, l, r);
        qsort(arr, l, index); // pivot値以下となる部分配列
        qsort(arr, index, r); // pivot値以上となる部分配列
    }

    public static void main(String[] args) {
        List<Integer> list = IntStream.range(0, 1000).mapToObj(Integer::valueOf).collect(Collectors.toList());
        Collections.shuffle(list);
        int[] arr = list.stream().mapToInt(Integer::intValue).toArray();
        qsort(arr, 0, arr.length);
        System.out.println(Arrays.toString(arr));
    }
}
IK.AM

クイックソート復習
