不意にはてブロの存在を思い出したので書きますが、タイトルの通りです。他に何もありません。クイックソートの説明は面倒なのでしていません (誰がこの記事を読むのだろうか)

動機

久しぶりに競プロ以外でコードを書きたくなったので、書いたことのなかった結構速めのソートアルゴリズムを書いた。 ~~ついでに~~学校の課題に同じ内容のを提出した。

1

最初に書いたコード。ググって見つけたコードを適当にパクった（コピペではないので、セーフ）

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    RandomAccessIterator i = first, j = last - 1, pivot = first;
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

pivot として範囲の一番前方を選んでいるので、ソート済みの配列等が来ると計算時間が $\mathrm{O}(n^2)$ になる(死)。

2

先ほどのコードの問題点を解消するために、pivot の位置を工夫した。具体的には範囲の両端と真ん中の値の中央値とした。

実はこれはパクリではなく、普通に自分で考えた (だから何だと)

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    RandomAccessIterator i = first, j = last - 1,
                         pivot = first + (last - first) / 2;
    if(*i > *pivot) std::iter_swap(i, pivot);
    if(*pivot > *j) std::iter_swap(pivot, j);
    if(*i > *pivot) std::iter_swap(i, pivot);
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

これでソート済みの配列が飛んできても死ななくなった。

速度が気になったので、ランダムな $10^6$ 要素の順列のソートにかかった時間を測定した。 (ちなみに 100 回平均)

my sort   : 85.9655 ms
std::sort : 83.5029 ms

3

std::sort に負けて悔しいので改良した。

小さい $n$ では挿入ソートが最速という噂を夢の中で聞いたので、調べてみたら、確かにそうだった。 $n\le100$ なら挿入ソートに移行することにした。

template <class RandomAccessIterator>
void insertion_sort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    for(RandomAccessIterator i = first + 1; i < last; ++i)
        for(RandomAccessIterator j = i; j > first && *(j - 1) > *j; --j)
            std::iter_swap(j - 1, j);
}

template <class RandomAccessIterator>
void quicksort(RandomAccessIterator first, RandomAccessIterator last) {
    if(last - first <= 1) return;
    if(last - first <= 100) {
        insertion_sort(first, last);
        return;
    }
    RandomAccessIterator i = first, j = last - 1,
                         pivot = first + (last - first) / 2;
    if(*i > *pivot) std::iter_swap(i, pivot);
    if(*pivot > *j) std::iter_swap(pivot, j);
    if(*i > *pivot) std::iter_swap(i, pivot);
    while(true) {
        while(*i < *pivot) ++i;
        while(*pivot < *j) --j;
        if(i >= j) break;
        std::iter_swap(i, j);
        ++i;
        --j;
    }
    quicksort(first, i);
    quicksort(j + 1, last);
}

これって多分だけど最悪計算量は落ちてませんよね。

んで測定

my sort   : 75.2429 ms
std::sort : 89.9799 ms

俺の勝ち。なんで負けたか明日までに考えといてください。そしたら何かが見えてくるはずです。

おわりに

std::sort は最悪計算時間が $\mathrm{O}(n \log n)$ だったと思うので、それを考えると勝利ではない (Hack される可能性がある)

cpprefjp には、std::sort はイントロソートで実装されていることが多いみたいな記述があった。クイックソートとヒープソートを組み合わせる的なやつらしい。

Series_205 のいろいろ

クソ記事の掃きだめ

クイックソートを、かいた

動機

1

2

3

おわりに