---
title: クイックソート復習
tags: []
categories: ["Programming", "Algorithm", "Sort", "QuickSort"]
date: 2014-03-21T19:56:42Z
updated: 2014-03-21T19:56:42Z
---

いつも忘れる

    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));
        }
    }