クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。

n個のデータをソートする際の最良計算量および平均計算量はO(n log n)である。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^2)である。また数々の変種がある。安定ソートではない。

6.1 アルゴリズムの説明

クイックソートは分割統治法を使用して、リストを2つのサブリストに分割します。具体的なアルゴリズムは次のとおりです。

シーケンスから要素を選択し、それを「ピボット pivot」と呼びます。
シーケンスを並べ替えると、ベンチマーク値よりも小さいすべての要素がベンチマークの前に配置され、ベンチマーク値よりも大きいすべての要素がベンチマークの後ろに配置されます（同じ番号をどちらの側にも配置できます）。パーティションが終了した後、ベンチマークはシーケンスの途中にあります。これは分割（partition）と呼ばれます。
二分割された各々のデータを、それぞれソートする

6.2 可視化デモ

6.3 実装

　　/**
     * クイックソート
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int[] QuickSort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end) return null;
        int smallIndex = partition(array, start, end);
        if (smallIndex > start)
            QuickSort(array, start, smallIndex - 1);
        if (smallIndex < end)
            QuickSort(array, smallIndex + 1, end);
        return array;
    }
    /**
     * クイックソートアルゴリズム-分割partition
     * @param array
     * @param start
     * @param end
     * @return
     */
    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        int smallIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++)
            if (array[i] <= array[end]) {
                smallIndex++;
                if (i > smallIndex)
                    swap(array, i, smallIndex);
            }
        return smallIndex;
    }

    /**
     * 配列内の2つの要素を交換する
     * @param array
     * @param i
     * @param j
     */
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

6.4 性能評価

最良時間計算量：T(n) = O(nlogn)
最悪時間計算量：T(n) = O(n^2)
平均時間計算量：T(n) = O(nlogn)