0525デフォルトの名無しさん (ワッチョイ cad4-UKyl)
2018/12/15(土) 23:22:08.85ID:BLCVn7NJ0ソートとコンパイラの最適化について教えて頂きたいのですが、
挿入ソートを書いてその実行時間を計測しました。
動的に確保した10000の要素数を持つ配列に、rand()関数でランダムな値を入れて、
clock()関数でソート時間を計測しています。
コンパイラはMinGWから入れたGCC6.3.0で、-O1と-O無しで実行時間にかなりの差が出ます。
バブルソートや選択ソートでは極端に大きな差が出ないのですが、挿入ソートだけはかなり差が出ます。
-O無しだと7秒前後、-O1だと1.7秒ほどで完了します。
自分が書いた挿入ソートが正しい内容になっているかと、
このプログラムでの最適化でどのようなことが行われているのかおおまかに教えて頂きたいです。
挿入ソートは以下の様に書きました。
void insersion_sort(unsigned array[], unsigned length)
{
register unsigned *start = &array[0];
register unsigned *sorted = start;
register unsigned *end = &array[length - 1];
while (sorted < end) {
register unsigned *crnt = sorted + 1;
while (crnt > start && *crnt < *(crnt - 1)) {
swap(crnt, crnt - 1);
crnt--;
}
sorted++;
}
}