並べ替えのアルゴリズム：応用編

予備知識

• アルゴリズムとは？
• 文章構成

動作手順までの内容

https://zenn.dev/algorithm_math/articles/548c3fe8d7b937#並べ替えのアルゴリズムで出来ること

変数定義追加

• $p$ : $n$ 以上の数で最も近い底2の累乗
• $k$ : ある対数の底

挿入ソート

1. 最初の要素はソート済みと見なす。
2. 次の要素を選び、ソート済みの部分に適切な位置へ挿入する。
3. すべての要素を順番に処理するまで繰り返す。
   

挿入ソートの一般化

組合せ数	3	5	6	5	3
記号表記	${}_3 \mathrm{C}_1$	${}_3 \mathrm{C}_2+{}_2 \mathrm{C}_1$	${}_3 \mathrm{C}_3+{}_2 \mathrm{C}_1×{}_2 \mathrm{C}_1+{}_1 \mathrm{C}_1$	${}_3 \mathrm{C}_2+{}_2 \mathrm{C}_1$	${}_3 \mathrm{C}_1$

シェルソート

1. 配列の長さに基づいて初期の間隔を決める。
2. 間隔ごとに、離れた要素同士を比較しながら挿入ソートを行う。
3. 間隔を徐々に縮めて、再度ソートを繰り返す。
   

シェルソートの一般化

マージソート

1. 配列を半分に分割する。
2. 分割した配列をさらに細かく分け、要素1つになるまで繰り返す。
3. 小さな配列同士をソートしながら結合する。
4. すべての要素が結合されるまで繰り返す。
   

マージソートの一般化

データ個数が底2の累乗でないとき
その差の分だけ各分割段階における比較回数が減る
上記の場合なら$8-5=3$だけ各段階で減る
各分割段階において最小単位1まで分割が済んだ部分については
次の分割段階へ移行しないため
その分だけ、さらに比較回数が減る

冒頭の計算量の式はこれらを表した式になっている