ALDS_1_1_A: Insertion Sortを解く話
挿入ソートを実装する．
特徴
- 未ソート部とソート済み部に分けてソート
- トランプの手札を並べ替える感じ
- 挿入ソートの改良版がシェルソート
アルゴリズム
これ．
二重ループの外側と内側の進む向きが違うので注意．
計算量
内側のループのたびに要素が移動する最悪のケースを考えると
最大次数の項以外は無視するので，挿入ソートの計算量は
実装
gist9bc97b8b935211285ee025a9312ee372
感想
直感的でわかりやすいアルゴリズムだと思う．
先日，友人と大富豪をやったときも手札の並べ替えに挿入ソートを意識していた．
