三区分割クイックソートと挿入ソートのハイブリッド実装
クイックソートは平均計算量が O(n log n) である一方、ピボット選択が悪い場合に最悪 O(n²) に退化する。本稿では、Java で実装可能な高速化テクニックを段階的に紹介する。
1. 単純な二方向分割
ピボットを末尾に固定したまま、slow / fast という２つの走査ポインタを使って「ピボット未満」を左に集める手法。
static void basicQuick(int[] a, int lo, int hi) {
...
7月5日 18:24 投稿