初心者のC言語とアルゴリズム

初心者のためのC言語とアルゴリズムの解説

AOJ(会津オンラインジャッジ)のALDS問題を解く

初めまして。 記念すべき初投稿です。 記念と言っても、私にしかあまり関係ありませんね(笑)。

今回からC言語を用いてAOJのADSL問題を解いていきたいと思います。 以下はAOJへのリンクとなります。

AIZU ONLINE JUDGE: Programming Challenge

オンラインジャッジを利用する理由は、解答の正誤判定がとても簡単に行えるからです。 自分でサンプルの入力などを作ったりするのは正直めんどくさいですね。

では、今回はADSL1_1_A Insertion Sort問題を解いていきましょう。 問題はリンク先を開き、COURSE→Algorithms and Data Structure I → Getting Started → Insertion Sortの順で見ることができます。 ユーザー登録などは不要です。(オンラインジャッジを利用するためには登録が必要です。)

解答は以下のようになります。 f:id:ginkgonut0:20170618192008p:plain

これは問題文にも擬似コードが書かれているので特に問題はないのではないでしょうか。 計算量はO(N2)になります。また、挿入ソートは離れた要素を直接変更することはないので、安定なソートアルゴリズムとなります。