全ソートアルゴリズム入場！地下ソート場最大トーナメント！

全ソートアルゴリズム入場！地下ソート場最大トーナメント！ Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

自己紹介さめ(мег-сск) 🧑‍💻 フリーランスのソフトウェアエンジニア 🧑‍🎓 社会人学生として通信制大学在学中得意分野: 📸
コンピュータビジョン (画像認識/点群処理) 🌍 空間情報処理 (地理情報/リモートセンシング) ☁️ クラウドインフラ設計/IaC (AWS, GCP) GitHub YouTube Speaker Deck

今日話すこと「最強のソートアルゴリズム」を決めるトーナメントを開催するッ！最大ソートアルゴリズムのトーナメントの意外な決着とはッ！？「最強」とは？刃牙を読んだことのない人は意味不明なネタですみません...

ソートとはッ！？ソートとはデータを特定の順序に並べ替えること人類は研鑽を積み様々なソートアルゴリズムを開発してきた... Credit: Learning Functional Data Structures And
Algorithms

代表的なソートアルゴリズムマージソートクイックソートヒープソート and so on... 誰もが思った、「最強のソートアルゴリズム」はどれか？
今夜、「最強のソートアルゴリズム」を決めるトーナメントを開催ッ！

全アルゴリズム入場！ Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

クイックソートッ！ピボット選択は生きていた!!更なる分割を積みインプレース凶器が甦った!!! 武神!!クイックソートだァ――――!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

ヒープソートッ！並べたいからここまできたッ　最初の考案者は不明!!!! 完全二分木のピットファイター　ヒープソートだ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

ティムソートッ！ Pythonistの前でならオレはいつでも全盛期だ!! 燃える闘魂　ティム・ピーターズのティムソート　本名で登場だ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

マージソートッ！めい土の土産にメモリーとはよく言ったもの!! フォン・ノイマンの奥義が今　実戦でバクハツする!!　ロスアラモス流ソート術　マージソートだ―――!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

イントロソートッ！ソートは実装で使えてナンボのモン!!!　超実戦 C++術!! 本家STLからイントロソートの登場だ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

シェルソートッ！挿入ソートだったらこのアルゴリズムを外せない!!　超Ａ級ソート師　シェルソートだ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

スムースソートッ！ほとんどソート済みの数列のソートはこのアルゴリズムが完成させた!! ダイクストラの切り札!!　スムースソートだ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

ペーシェンスソートッ！ソリティア四千年の歴史が今ベールを脱ぐ!!　最長増加部分列から　ペーシェンスソートだ!!! Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

以上8名によってベルト争奪戦を行いますッ！ Credit: 板垣恵介、「グラップラー刃牙」21巻 (秋田書店)

地下ソート場最大トーナメントの意外な決着ッ！

全員引き分け、全員優勝！全試合が引き分けとなり、全員優勝となりました！なぜ格闘漫画だったら読者からのブーイング必須な結果になってしまったのか？

ソートアルゴリズムの理論下限

ソートアルゴリズムの理論下限ソートアルゴリズムはこれ以上速くできない理論下限がある今日の選手はすべてこの理論下限に達していたなぜソートにはこれ以上速くできない理論下限があるのか？

すべての並び替えの組み合わせの数個の数値を並び替える組み合わせの数は、通り通りの中からたった一つの正解を見つける必要がある n n! n!

二分木の高さと葉の数二分木の高さをとすると、最大で個の並べ替えの組み合わせを比較できる h 2h

必要な木の高さは？すべての数字の並びを比較するにはが必要！ n! ≤ 2h

スターリングの公式ガンマ関数(階乗の一般化)を近似できる便利な公式 n! ≈ 2πn ( e n
) n

木の高さを求める不等式を解く左辺をスターリングの公式で近似すると n! ≤ 2h log n! ≤ 2
h log n! ≈ 2 log 2 ( 2πn ( e n ) n )

さらに計算していく残った3つの項のうち、最も大きな項が計算量に影響する一番大きな項は？ log + 2 2πn n
log 2 ( e n ) log (2πn) + 2 1 2 n log n − 2 n log e 2

数学的補足: 計算量の表現記法上界: 、必要な計算量の上限下界: 、最低でも絶対に必要な計算量厳密計算量: 、上界と下界が一致する場合 O(⋅) Ω(⋅)
Θ(⋅)

オーダーの比較 👈 これが一番大きい一番計算量が多い項はが十分に大きくなると、この項以外は無視してもOK！ log (2πn)
= 2 1 2 O(log n) n log n = 2 O(n log n) n log e = 2 O(n) n log n 2 n log n! = 2 O(n log n)

数列をソートするのに必要な木の高さは？いろんな近似をしているが、計算量の下界( ) の観点からは厳密に正しく、等号が成り立つ h ≥ log n!
= 2 Ω(n log n) Ω(⋅)

ソートアルゴリズムの「最速」どんなにソートの計算を効率化しても、の計算量は避けられないこれが理論上最速、これ以上に速い「汎用的」なソートアルゴリズムは存在しない！ Ω(n log n)

今日の選手たちの「平均」計算量クイックソート: ヒープソート: マージソート: and so on... 今日の選手たちは皆、平均計算量は理論下限のに達していた！だから全員引き分けの全員優勝！
O(n log n) O(n log n) O(n log n) O(n log n)

各アルゴリズムの得意・不得意

クイックソート平均計算量は最悪計算量は長所: インプレース(追加メモリ不要) 短所: 最悪計算量が逆順に並んでいる場合、最悪計算量になる (5, 4,
3, 2, 1, 0) → (0, 1, 2, 3, 4, 5) と並べ替えるのは苦手 O(n log n) O(n ) 2 O(n ) 2

ヒープソート平均計算量は最悪計算量は長所: 最悪計算量が、インプレース短所: 不安定ソート(ソート途中で順序が維持されない)、ランダムアクセスが必要
(並列化が難しい) O(n log n) O(n log n) O(n log n)

マージソート平均計算量は最悪計算量は長所: 最悪計算量が、安定ソート短所: 追加でのメモリが必要元々の数列以外にもう一つの数列を覚えておく
必要がある小さな数列の場合はメモリを確保するのがオーバーヘッドになる O(n log n) O(n log n) O(n log n) O(n)

ソートアルゴリズムの使い分け一般的な用途 → クイックソート（多くの言語の標準）安定性が必要 → マージソートリアルタイム性重視 →
ヒープソート（最悪保証かつインプレース）ソートアルゴリズムに「最強」は存在しない得意・不得意があり、「最適」があるのみ

特定条件下で強いアルゴリズム平均パフォーマンスでは今日のトーナメント出場選手たちに劣るが、特定条件下ではより高速基数ソート: 入力データが限定されている場合に有効カウンティングソート: 値の範囲が小さい場合に有効バケットソート: 入力データが一様分布している場合に有効 O(kn)
O(n + k) O(n)

まとめソートアルゴリズムに「最強」は存在しない得意・不得意があり、「最適」があるのみ汎用的にはパフォーマンスが劣っていても、特定条件下では圧倒的に強くなるアルゴリズムもあるみんなちがって、みんないいそれぞれの特性を把握して、状況に応じた適切なアルゴリズムを選ぶことが重要！

おまけただしバブルソート、テメーはダメだ「最強」は存在しないが明確な悪手は存在する Leet Codeだとバブルソート的な計算量のアルゴリズムはTLEになるので効率化が重要！ Credit: 澤井啓夫、「ボボボーボ・ボーボボ」1巻 (集英社)
O(n ) 2

全ソートアルゴリズム入場！地下ソート場最大トーナメント！

全ソートアルゴリズム入場！地下ソート場最大トーナメント！

More Decks by Syota-Sasaki

Other Decks in Technology

Featured

Transcript