(6.1.1) 「a[i] > a[i+1] を満たす i があったら a[i] と a[i+1] とを交換する。これをくり返してゆく」 というのがこのソートのアイディアである。 幼稚園の先生が園児を背の順に並ばせるとき， この方法を採用することもあるだろう。 そのような i のさがし方はいろいろ考えられる。 （そのうちのどれを採用するかをきちんと述べるまでは， これをアルゴリズムとは呼べない。）
(6.1.2) 次に示すのはその一つのやり方である。
これで，最大の値をもつもの（のうちの一つ）が a[N] にはいることを（頭の中で）確かめよ。 （幼稚園の先生が園児を背の順に並ばせる過程でいえば， どんな手順をとったことになるか？）
次に
これで，a[1] から a[N-1] までのうちで最大のもの （＝配列全体で言えば二番目に大きいもの）が a[N-1] にはいった。 以下はこれのくり返し。
(6.1.3) このアルゴリズムでの比較回数は (N-1) + (N-2) + ... + 2 + 1 = N(N-1)/2, すなわち， およそ N2/2 である。 交換回数は最悪の場合（＝完全に逆順に並んでいた場合）が比較回数と同じ， 最も lucky な場合（＝元々ソートされていた場合）が 0 で， 平均するとおよそ N2/4 とみてよいだろう。 よって，全体では Ο(N2) のアルゴリズムである。
(6.1.4) 興味のある人は， このアルゴリズムでソートを行なうプログラムを書き， 実行にかかる時間を計ってみよ。
(6.2.1) a[1] から a[i] までのうちで最大のものの添え字を求める操作を i-1 回の比較で行なう方法が存在する。 このことは容易だから認めよう。
(6.2.2)
これでソートが完了する。
(6.2.3) 全体の比較回数は (N-1) + (N-2) + ... + 1 = N(N-1)/2 回， 交換回数は N-1 回である。 （最大のものが最後にきていても，すなわち，交換の必要がなくても swap() を呼び出すほうが全体としては速い。 よって， 交換回数は「たかだか N-1 回」ではなくちょうど N-1 回である。）
(6.2.4) 以上から， このソートの比較回数は Ο(N2) であり， 交換回数は Ο(N) であることがわかる。 全体では Ο(N2) のアルゴリズムである。
(6.2.5) 興味のある人は， このアルゴリズムでソートを行なうプログラムを書き， 実行にかかる時間を計ってみよ。
(6.2.6) ※ a[1] から a[i] までのうちで最大のものの添え字を求める際には， j < i なる j に対し a[1] から a[j] までで最大の値を持つものの添え字を保持しておくわけだが， より速いプログラムを書くなら，そこまでの最大値そのものも保持しておくほうがよい。
(6.3.1) ここは，時間に余裕がある人向けの節である。
(6.3.2) 配列の要素 a[i] と a[j] を比較するには if (a[i] > a[j]) のように書くわけだが， これを次のような関数にしよう。
int comp(int i, int j) {
return a[i] - a[j];
}
こう定義したうえで if (comp(i, j) > 0) と書けば， スピードの点で若干劣るが，同じことである。 プロトタイプ宣言も付け足しておくこと。
(6.3.3) 次のように書き足すと，比較回数，交換回数を調べることができる。
#include ...
int ccount = 0; /* 比較（comp()）のカウンタ。0 で初期化 */
int scount = 0; /* 交換（swap()）のカウンタ。0 で初期化 */
main() {
int i, j;
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………田中美佐子\n"); /* 自分の氏名を出力 */
init();
/* ここは上で書いたソートの部分 */
printf("%d 回比較しました.\n", ccount); /* 比較回数を出力 */
printf("%d 回交換しました.\n", scount); /* 交換回数を出力 */
}
void swap(int i, int j) {
...
scount++; /* ここを通るたびにカウンタが増える */
}
int comp(int i, int j) {
ccount++; /* ここを通るたびにカウンタが増える */
return a[i] - a[j];
}
関数 comp() が呼び出されるたびに変数 ccount の値が増されるので，
これで comp() が呼び出された回数がわかる。
変数 scount についても同様。
(6.3.4) 実験し，比較回数・交換回数が前に書いた値に近いことを確認しよう。