整列アルゴリズムを比較する(準備編)

どうも、フライでないポテト君です(?)

ということで今回はC++で整列アルゴリズムを作っていきます。
整列は複数のデータを、表す値の大きさで降順または昇順で並び替えることです。

今回は、交換法(バブルソート)、選択法、挿入法、改良挿入法(シェルソート)、クイックソート、ヒープソート、マージソートを、それぞれ、整列されていない少量/多量データ、既に降順/昇順でソートされたデータで実行時間を比較していきます。

それぞれのアルゴリズムの詳細や具体的な比較方法は後で説明します。
(もちろんアルゴリズムは多少は人によって書き方が違ったりします。)

整列アルゴリズムでは、実行時間を比べるために計算量(オーダ記法)というものがよく使われます。
(実際これは実行時間を比較するのに大して役に立たないことも多く、例えばプログラムAがプログラムBより計算量が少ないからといって、Aが速いというわけではなく、Bの方が速くなることもあります。意味ある？)
これは、プログラムの計算の実行回数を大まかに表現したものです。(この大まかにというところが一番の特徴であり欠点でもあるのですが)

例えば次のプログラム
int a;
は１回のみ処理を行うので、計算量はO(オーダと読みます)(1)です。
次のプログラム(nは定数)は
for(int i=0;i<n;i++){
    a+=i;
}
これは、n回実行するので、O(n)です。
じゃあこれはどうでしょうか
int a;
int a=n;
for(int i=0;i<n;i++){
    a+=i;
    for(int j=0;j<n;j++) a+=i;
}
1+1+n(1+n)でn^2+n+2でしょうか?
O(n^2)です…
計算量は、次数の小さい項、項の係数を無視します。
無視はよくないよ！(小並感)
まあ定義なのでそうしないとなんですが…w
nが十分に大きいときに無視できるらしいですが、係数は無視できんだろ(((((

それぞれのアルゴリズムの計算量ですが、全てについて解説するつもりはないです。少しは話すかもしれません。

ということで、準備編は終わりです。
次回は交換法からそれぞれのアルゴリズムの作成をやっていきます！