今までのようにループ回数から計算量を直感的に求められないアルゴリズム。 挿入ソートは、整列されていれば高速に動作し、そうでない場合にはN(N-1)/2よりO(N^2)のアルゴリズムに なるのだった。この特徴を生かし、あらかじめざくっと(３個ずつとか４個ずつ…

ソートが安定的か判定する。と言っても、バブルソートを安定的として、選択ソートの結果と先頭から 単純に比較していく。先頭から比較していくだけなので、計算量はデータNに対してN回になる。これだけではつまらないので、N^4となるアルゴリズムでも実装し…

あらかじめ床に並べられたトランプを見ていき(j)、 一番小さい数を先頭の数と交換する。 そうすると、比較した回数分、先頭からはソート済みになるので、 次の比較は先頭から比較した回数ぶん後ろ(i)から見ればよい。選択ソートでは、離れた要素を交換するの…

挿入ソートと違い、あらかじめ床に並べてあるトランプを整列させる。 (結局全部並べた暁には、メモリの使用量は同じだけれど・・・。)考え方は簡単で、一番後ろの要素から一つずつ比較していく。 全要素比較したあとでは、要素がソートされている。 ここでは…

ソートは計算量の見積もり練習として良い題材となる。 (for文から直感的に見積もることができるから。) for文はプログラム中でも頻繁に使うため、実践的である。初等とは、効率が悪い事もあるが、実装が簡単という意味である。以下にアルゴリズムを紹介する…