初等ソート

ソートは計算量の見積もり練習として良い題材となる。
(for文から直感的に見積もることができるから。)
for文はプログラム中でも頻繁に使うため、実践的である。

初等とは、効率が悪い事もあるが、実装が簡単という意味である。

以下にアルゴリズムを紹介する。

１、挿入ソート
トランプを床に並べてソートするときに行うとイメージしやす
い。
まず、引いたトランプ(対象)と床に並べたトランプを比較する。
トランプが収まる位置を作るように、挿入する位置から右(左)のすべてのカードを一枚分ずらし、
対象のトランプを挿入する。
これを繰り返す。

計算量について、最初から昇順(降順)にならんでいる場合は、トランプでいうと床に並べていくだけなので、
トランプN枚に対してN回で済む。

一方、最悪の場合は逆順にならんでいた場合で、各iのループでi回(jのループ回数)ループが発生するので、
1 + 2 + 3 + … + (N-2) + (N-1) = N(N-1)/2
となる。
(高校でやる等差数列の公式「初項 a，公差 d，項数 n，末項lの等差数列の初項から第 n 項までの和 Sn はSn=n(a + l) /2」より)

このため、挿入ソートはデータの初期の並び順で計算回数が大きく影響を受ける。

コーディングとしては、「A[j + 1] = v」が引っかかった。
これは、条件でブレークした際、j--されるため、j+1が挿入位置となる。

■ソース
https://github.com/JunKojima/algorithm/blob/master/3-2_insertsort.c

■参考書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造