刹那式
刹那式（せつなしき）は、二分挿入ソートを応用した、差分ソートです。
ソート済み配列に対し、値の変更を行った箇所に焦点を当て、超高速にソートします。
以下の特徴があります。
- 比較ソート
- 安定ソート
- 外部領域：無し
- 平均時間：比較O(log N)、移動O(N/2)
- 最悪時間：比較O(log N)、移動O(N)
- 最良時間：比較O(2)、移動O(0)
- 再帰：無し
リポジトリ
基本となるアルゴリズム
- ソート済み配列に対して、任意の位置の値を変更します。
- （変更位置の値 ＜ 変更位置の下の値）であれば、下方を二分探索し、変更位置から探索位置を回転します。
- （変更位置の上の値 ＜ 変更位置の値）であれば、上方を二分探索し、変更位置から探索位置を回転します。
具体的な流れ
ソート済み配列に対して、任意の位置の値を変更します
0 1 2 4 5 6 7 9|ソート済み配列
↓
0 1 2 4 x 6 7 9|任意の位置の値を変更
（変更位置の値 ＜ 変更位置の下の値）であれば、下方を二分探索し、変更位置から探索位置を回転します
0 1 2 4 5 3 7 9|[5]=3の場合
0 1 2 4 5|. . .|下方を二分探索
. . .|3 4 5|. .|変更位置から探索位置を回転
0 1 2 3 4 5 7 9|ソート結果
（変更位置の上の値 ＜ 変更位置の値）であれば、上方を二分探索し、変更位置から探索位置を回転します
0 1 8 4 5 6 7 9|[2]=8の場合
. . .|4 5 6 7 9|上方を二分探索
. .|4 5 6 7 8|.|変更位置から探索位置を回転
0 1 4 5 6 7 8 9|ソート結果
ビルド＆テスト
環境は以下のとおりです。
- Windows 10 Pro 64bit
- Core i7-8700 3.20GHz
Msvc
Microsoft(R) C/C++ Optimizing Compiler Version 19.15.26732.1 for x64
Microsoft (R) Incremental Linker Version 14.15.26732.1
cl Main.cpp -Ox -EHsc -Fe:TestMsvc.exe
TestMsvc.exe
clang++
clang version 7.0.0 (tags/RELEASE_700/final)
Target: x86_64-w64-windows-gnu
clang++ Main.cpp -O3 -o TestClang++.exe
TestClang++.exe
g++
gcc version 8.2.0 (Rev3, Built by MSYS2 project)
Target: x86_64-w64-mingw32
g++ Main.cpp -O3 -o TestG++.exe
TestG++.exe
平均ベンチマーク
以下は、ソート済み配列に対し、ランダムな位置を、ランダムな値に変更した場合です。
単位は秒で、数値が低いほど高速です。
Msvc
| 件数 | std::sort | std::stable_sort | 刹那式 |
|---|---|---|---|
| 10,000 | 0.00007095 | 0.00004502 | 0.00000115 |
| 1,000,000 | 0.00975892 | 0.00698905 | 0.00009487 |
| 100,000,000 | 0.27018098 | 1.26169269 | 0.01670523 |
clang++
| 件数 | std::sort | std::stable_sort | 刹那式 |
|---|---|---|---|
| 10,000 | 0.00006162 | 0.00006669 | 0.00000050 |
| 1,000,000 | 0.00775640 | 0.00978430 | 0.00006938 |
| 100,000,000 | 0.99487866 | 1.46673092 | 0.01248609 |
g++
| 件数 | std::sort | std::stable_sort | 刹那式 |
|---|---|---|---|
| 10,000 | 0.00009420 | 0.00006123 | 0.00000040 |
| 1,000,000 | 0.01269281 | 0.00870394 | 0.00006129 |
| 100,000,000 | 1.32669707 | 1.32506381 | 0.01232715 |
特性ベンチマーク
以下は全て、「100,000,000」件でソートしました。
単位は秒で、数値が低いほど高速です。
最悪ケース１
ソート済み配列に対し、先頭を最大値に変更した場合です。
| std::sort | std::stable_sort | 刹那式 | |
|---|---|---|---|
| Msvc | 0.28328255 | 1.27838705 | 0.03301556 |
| clang++ | 0.94680632 | 1.49072315 | 0.02450915 |
| g++ | 1.24406811 | 1.35104790 | 0.02465655 |
最悪ケース２
ソート済み配列に対し、末尾を最小値に変更した場合です。
| std::sort | std::stable_sort | 刹那式 | |
|---|---|---|---|
| Msvc | 0.29024827 | 1.27097092 | 0.03784692 |
| clang++ | 6.59369224 | 1.44779880 | 0.02844831 |
| g++ | 7.05050788 | 1.30785120 | 0.02579642 |
最良ケース
ソート済み配列に対し、値を変更せずに、位置をランダムにした場合です。
| std::sort | std::stable_sort | 刹那式 | |
|---|---|---|---|
| Msvc | 0.26143167 | 1.24644350 | 0.00000026 |
| clang++ | 0.99570890 | 1.44735863 | 0.00000031 |
| g++ | 1.33114203 | 1.30589223 | 0.00000050 |
余談
如何だったでしょうか？
ソートは、常に全体で行う必要はないという観点から、差分ソートという考えに至ったアイデアです。
本来であれば、全体ソートである std::sort と std::stable_sort との比較はフェアではないのですが、差分ソートの有用性を判断していただくには必要かと思い、ベンチマークを掲載することにしました。
参考になれば幸いです。
上手く運用すれば、激速なパフォーマンスが得られますが、使い方を誤ると激遅になる諸刃の剣。
ソートアルゴリズムには、まだ浪漫が残っています。
以下の記事も併せて読んでいただけると、より楽しめるかも知れません。