クイックソート | Programming Place Plus アルゴリズムとデータ構造編【整列アルゴリズム】 第６章

トップページ – アルゴリズムとデータ構造編 この章の概要 🔗 この章の概要です。 クイックソート クイックソートのプログラム例 再帰しないクイックソートの実装 クイックソートの性能 最悪の場合 基準値の選び方 まとめ 練習問題 参考リンク 更新履歴 クイックソート 🔗 この章では、クイックソートを取り上げます。 クイックソートは、その名のとおり、非常に高速なソートを実現するアルゴリズムです。 具体的には、平均計算量が O(n log n)であり、対象のデータ列に事前に何らかの制約を要求しない汎用的なソートアルゴリズムとしては理論上、最高性能となります。 しかし、クイックソートの最悪時の計算量は O(n2)です。これはバブルソート（第３章）などの遅いソートアルゴリズムと同等です。 このように性能のふり幅がとても大きいのですが、最悪のケースは、実装を工夫することでほぼ避けられます。この辺