テクノロジ系 / アルゴリズムとプログラミング
クイックソート
クイックソートは、基準値を選んで小さいグループと大きいグループに分け、再帰的に整列するアルゴリズムです。
別名・関連表記：クイック
もう少し詳しく
ピボットと呼ばれる基準値を使って配列を分割し、それぞれの部分配列を同じ手順で整列します。平均的には高速ですが、ピボットの選び方が悪いと偏った分割になり、性能が落ちることがあります。
試験での見方
例：基準値50を選び、50未満のグループと50以上のグループに分けてから、それぞれをさらに同じ方法で並べ替えます。
分割統治、ピボット、再帰という語が出たらクイックソートを意識します。安定ソートではない点、平均計算量は O(n log n) だが最悪では O(n^2) になり得る点も押さえましょう。