読者です 読者をやめる 読者になる 読者になる

ALDS_1_1_A: Insertion Sortを解く話

挿入ソートを実装する.

 

特徴

  • 未ソート部とソート済み部に分けてソート
  • トランプの手札を並べ替える感じ
  • 挿入ソートの改良版がシェルソート

 

アルゴリズム

これ.

www.youtube.com

二重ループの外側と内側の進む向きが違うので注意.

 

計算量

内側のループのたびに要素が移動する最悪のケースを考えると

 1 + 2 + ... + N - 1 = (N^2 - N) / 2

最大次数の項以外は無視するので,挿入ソートの計算量は

 O(N^2)

 

実装

gist9bc97b8b935211285ee025a9312ee372

 

感想

直感的でわかりやすいアルゴリズムだと思う.

先日,友人と大富豪をやったときも手札の並べ替えに挿入ソートを意識していた.