Tools + Simulatorsnanase.cc / tools

ソート

クイックソート（末尾をピボット）

比較・読み取り交換・書き込み
0 / 0 回
速さ 速さ

回/秒

交換

選択

挿入

マージ

分割

非比較

ネットワーク

遅い

要素数 要素数

個

全操作
0回
比較
0
交換
0
読み取り
0
書き込み
0
最良
平均
最悪
補助メモリ
安定性

音量 音量

dB

鳴らす操作
音色

高さ

動作原理と式

操作の数え方

  • 比較: 2 つの要素、または要素と手元の値を比べる 1 回
  • 交換: 2 つの要素を入れ替える 1 回
  • 読み取り: 配列か補助配列の値を手元へ取る 1 回。比較の分は数えない
  • 書き込み: 配列か補助配列へ値を置く 1 回

比較の回数の下限

比較だけで並べ替えるには、n! 通りの並びを見分ける必要があります[1]。

Cmin≥⌈log2n!⌉≈nlog2n−1.44n

計数・基数などの非比較のソートは、値そのものを使うのでこの下限を受けません。

データとの相性

  • 挿入: 移動の回数は順序が逆の組（転倒）の数に等しい。ほぼ並び替え済みなら少ない
  • 末尾をピボットにするクイック: 並び替え済みでは毎回 1 個しか分かれず、比較は n(n−1)/2 回
  • 3 分割クイック: ピボットと等しい値をまとめて除くので、値の種類が少ないと速い
  • ティム・パワー・スムース: すでに並んだ部分を活かす
  • ソーティングネットワーク: 比べる位置が初めから決まっていて、比較の回数はデータによらない

音

値 v の音の高さを次の式で決めます。比較では 2 つの値、交換では入れ替えた 2 つの値を鳴らします。値を音にする発想は The Sound of Sorting にならいました[2]。

f=110×24(v−1)/(vmax−1) Hz

計算量

n は要素数、k は値の範囲、d は桁数です。「不明」は一般の式が知られていないものです。

名前最良平均最悪補助メモリ安定性出典
バブルソート𝑛𝑛²𝑛²1安定[1]
シェーカーソート𝑛𝑛²𝑛²1安定[1]
コムソート𝑛 log 𝑛不明𝑛²1不安定[3][4]
ノームソート𝑛𝑛²𝑛²1安定[5]
奇偶転置ソート𝑛𝑛²𝑛²1安定[6]
選択ソート𝑛²𝑛²𝑛²1不安定[1]
双方向選択ソート𝑛²𝑛²𝑛²1不安定
ヒープソート𝑛 log 𝑛𝑛 log 𝑛𝑛 log 𝑛1不安定[7][8]
スムースソート𝑛𝑛 log 𝑛𝑛 log 𝑛1不安定[9]
サイクルソート𝑛²𝑛²𝑛²1不安定[10]
パンケーキソート𝑛²𝑛²𝑛²1不安定[11]
挿入ソート𝑛𝑛²𝑛²1安定[1]
二分挿入ソート𝑛 log 𝑛𝑛²𝑛²1安定[1]
シェルソート𝑛 log 𝑛不明不明1不安定[12][13]
マージソート𝑛 log 𝑛𝑛 log 𝑛𝑛 log 𝑛𝑛安定[1]
ボトムアップマージソート𝑛 log 𝑛𝑛 log 𝑛𝑛 log 𝑛𝑛安定[1]
ティムソート（簡略版）𝑛𝑛 log 𝑛𝑛 log 𝑛𝑛安定[14]
パワーソート（簡略版）𝑛𝑛 log 𝑛𝑛 log 𝑛𝑛安定[15]
インプレースマージソート（SymMerge）𝑛 log 𝑛𝑛 log²𝑛𝑛 log²𝑛log 𝑛安定[16]
クイックソート（末尾をピボット）𝑛 log 𝑛𝑛 log 𝑛𝑛²log 𝑛不安定[17]
クイックソート（中央をピボット）𝑛 log 𝑛𝑛 log 𝑛𝑛²log 𝑛不安定[17]
クイックソート（3 値の中央値をピボット）𝑛 log 𝑛𝑛 log 𝑛𝑛²log 𝑛不安定[17][18]
3 分割クイックソート𝑛𝑛 log 𝑛𝑛²log 𝑛不安定[18]
デュアルピボットクイックソート𝑛 log 𝑛𝑛 log 𝑛𝑛²log 𝑛不安定[19][20]
イントロソート𝑛 log 𝑛𝑛 log 𝑛𝑛 log 𝑛log 𝑛不安定[21]
pdqsort（簡略版）𝑛𝑛 log 𝑛𝑛 log 𝑛log 𝑛不安定[22]
計数ソート𝑛 + 𝑘𝑛 + 𝑘𝑛 + 𝑘𝑛 + 𝑘安定[23]
基数ソート（LSD・基数 4）𝑑𝑛𝑑𝑛𝑑𝑛𝑛安定[23]
基数ソート（MSD・基数 4）𝑑𝑛𝑑𝑛𝑑𝑛𝑛安定[24]
アメリカンフラッグソート（基数 4）𝑑𝑛𝑑𝑛𝑑𝑛log 𝑛不安定[24]
バケットソート（√n 個）𝑛𝑛√𝑛𝑛²𝑛安定[23]
フラッシュソート𝑛𝑛𝑛²𝑛不安定[25]
ビーズソート𝑛𝑘𝑛𝑘𝑛𝑘𝑛不安定[26]
バイトニックソート𝑛 log²𝑛𝑛 log²𝑛𝑛 log²𝑛log 𝑛不安定[27]
バッチャーの奇偶マージソート𝑛 log²𝑛𝑛 log²𝑛𝑛 log²𝑛1不安定[27]
ペアワイズソート𝑛 log²𝑛𝑛 log²𝑛𝑛 log²𝑛1不安定[28]
ストゥージソート𝑛2.71𝑛2.71𝑛2.71log 𝑛不安定[29]
スローソート𝑛log 𝑛𝑛log 𝑛𝑛log 𝑛𝑛不安定[30]
ボゴソート𝑛𝑛·𝑛!∞1不安定[31]
ボゾソート𝑛𝑛!〜𝑛·𝑛!∞1不安定[31]

出典

  1. 基本のソート・比較の回数の下限D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998
  2. 操作を音にするT. Bingmann, The Sound of Sorting, 2013
  3. コムW. Dobosiewicz, “An Efficient Variation of Bubble Sort,” Information Processing Letters, vol. 11, no. 1, pp. 5–6, 1980
  4. コムの縮小率 1.3S. Lacey, R. Box, “A Fast, Easy Sort,” Byte, vol. 16, no. 4, pp. 315–316, 318, 320, 1991
  5. ノームH. Sarbazi-Azad, “Stupid Sort: A New Sorting Algorithm,” Newsletter, Dept. of Computing Science, Univ. of Glasgow, 599:4, 2000。D. Grune, Gnome Sort
  6. 奇偶転置N. Habermann, “Parallel Neighbor Sort (or the Glory of the Induction Principle),” CMU Computer Science Report, 1972
  7. ヒープJ. W. J. Williams, “Algorithm 232: Heapsort,” CACM, vol. 7, no. 6, pp. 347–348, 1964
  8. ヒープの作り方R. W. Floyd, “Algorithm 245: Treesort 3,” CACM, vol. 7, no. 12, p. 701, 1964
  9. スムースE. W. Dijkstra, “Smoothsort, an alternative for sorting in situ,” Science of Computer Programming, vol. 1, no. 3, pp. 223–233, 1982
  10. サイクルB. K. Haddon, “Cycle-Sort: A Linear Sorting Method,” The Computer Journal, vol. 33, no. 4, pp. 365–367, 1990
  11. パンケーキ（反転の回数）W. H. Gates, C. H. Papadimitriou, “Bounds for Sorting by Prefix Reversal,” Discrete Mathematics, vol. 27, no. 1, pp. 47–57, 1979
  12. シェルD. L. Shell, “A High-Speed Sorting Procedure,” CACM, vol. 2, no. 7, pp. 30–32, 1959
  13. シェルの増分M. Ciura, “Best Increments for the Average Case of Shellsort,” FCT 2001, LNCS 2138, pp. 106–117
  14. ティムT. Peters, listsort.txt, CPython, 2002
  15. パワーJ. I. Munro, S. Wild, “Nearly-Optimal Mergesorts: Fast, Practical Sorting Methods That Optimally Adapt to Existing Runs,” ESA 2018, LIPIcs 112, 63:1–63:16
  16. インプレース（SymMerge）P.-S. Kim, A. Kutzner, “Stable Minimum Storage Merging by Symmetric Comparisons,” ESA 2004, LNCS 3221, pp. 714–723
  17. クイックC. A. R. Hoare, “Quicksort,” The Computer Journal, vol. 5, no. 1, pp. 10–16, 1962
  18. 3 値の中央値・3 分割J. L. Bentley, M. D. McIlroy, “Engineering a Sort Function,” Software: Practice and Experience, vol. 23, no. 11, pp. 1249–1265, 1993
  19. デュアルピボットV. Yaroslavskiy, “Replacement of Quicksort in java.util.Arrays with new Dual-Pivot Quicksort,” OpenJDK core-libs-dev, 2009
  20. デュアルピボットの解析S. Wild, M. E. Nebel, “Average Case Analysis of Java 7’s Dual Pivot Quicksort,” ESA 2012, LNCS 7501, pp. 825–836
  21. イントロD. R. Musser, “Introspective Sorting and Selection Algorithms,” Software: Practice and Experience, vol. 27, no. 8, pp. 983–993, 1997
  22. pdqsortO. R. L. Peters, “Pattern-defeating Quicksort,” arXiv:2106.05123, 2021
  23. 計数・基数・バケットT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022
  24. 基数（MSD）・アメリカンフラッグP. M. McIlroy, K. Bostic, M. D. McIlroy, “Engineering Radix Sort,” Computing Systems, vol. 6, no. 1, pp. 5–27, 1993
  25. フラッシュK.-D. Neubert, “The Flashsort1 Algorithm,” Dr. Dobb’s Journal, vol. 23, no. 2, 1998
  26. ビーズJ. J. Arulanandham, C. S. Calude, M. J. Dinneen, “Bead-Sort: A Natural Sorting Algorithm,” Bulletin of the EATCS, vol. 76, pp. 153–162, 2002
  27. バイトニック・奇偶マージK. E. Batcher, “Sorting Networks and Their Applications,” AFIPS Spring Joint Computer Conference, vol. 32, pp. 307–314, 1968
  28. ペアワイズI. Parberry, “The Pairwise Sorting Network,” Parallel Processing Letters, vol. 2, no. 2–3, pp. 205–211, 1992
  29. ストゥージ（問題 7-3）T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 2nd ed., MIT Press, 2001
  30. スローA. Broder, J. Stolfi, “Pessimal Algorithms and Simplexity Analysis,” SIGACT News, vol. 16, no. 3, pp. 49–53, 1984
  31. ボゴ・ボゾH. Gruber, M. Holzer, O. Ruepp, “Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms,” FUN 2007, LNCS 4475, pp. 183–197

このツールで決めたこと

  • 値は 1〜n の整数
  • ほぼ並び替え済みは約 5 % の要素を近くの要素と入れ替えたもの
  • 「中央値付近に偏り」は平均 n/2、標準偏差 n/8 の正規分布
  • 「両端に偏り」は標準偏差 n/10 の正規分布の半分を両端から
  • 「値の種類が少ない」は 5 種類、「のこぎり」は 4 山
  • ティムとパワーは最小のランまで挿入で伸ばす。ギャロップはしない
  • pdqsort は分岐の少ない分割を使わない
  • 基数は 4、バケットは n 個、フラッシュの区分は 0.43n 個
  • シェルの増分は Ciura の 701 まで。要素数の上限は 1,024
  • ビーズは高い段から順に段ごとに全要素を読むので nk 回。論文の式は入力の総和に比例
  • ボゾは異なる 2 つを選んで交換する形。平均は交換が n! 程度、比較が n! 以上 n·n! 以下
  • 双方向選択は選択ソートの最小と最大を同時に選ぶ形
  • 操作は 3,000,000 回で打ち切る。比較の表示は 1,000,000 回、ボゴとボゾは 200,000 回
  • 速いときは 1 コマに 8 音まで間引く

関連ツール

すべてのツール