iOS開発におけるクイックソートのObjective-C実装
クイックソート（Quick Sort）はバブルソートの改良版です。
クイックソートはC. A. R. ホーアによって1962年に提案されました。基本的な考え方は以下の通りです：一度の処理でソート対象のデータを二つの独立した部分に分割し、一方のすべての要素がもう一方のすべての要素より小さくなるようにします。その後、この方法をそれぞれの部分に対して再帰的に適用することで ...
7月18日 17:44 投稿
三区分割クイックソートと挿入ソートのハイブリッド実装
クイックソートは平均計算量が O(n log n) である一方、ピボット選択が悪い場合に最悪 O(n²) に退化する。本稿では、Java で実装可能な高速化テクニックを段階的に紹介する。
1. 単純な二方向分割
ピボットを末尾に固定したまま、slow / fast という２つの走査ポインタを使って「ピボット未満」を左に集める手法。
static void basicQuick(int[] a, int lo, int hi) {
...
7月5日 18:24 投稿