(5.1.1) 以上で準備を終わり，この授業のテーマである「整列」にはいる。
88 98 20 82 31 53 22 10 12 91 92 79 95 50 19 58
整列とは，上のような有限数列が与えられたとき， それらを小さい順に並べかえることである。 整列は「ソート (sort)」とも言う。 ただし， 「整列」「sort」の日常用語としての意味はこれとは少し違う。
(5.1.2) 次のプログラムを元に， 順次，書き足したり改良したりしてゆくが， ソースファイル名は指定しないので，適当に決めよ。 ファイル名をプリントにメモしておくと， あとで探すときに楽かも。
(5.1.3) ※ 実際の仕事でコンピュータを使う際には， 数だけを並べかえたのでは意味がないのが普通である。 たとえば， 受験者一人一人に対応するデータ 「受験番号，国語の得点，数学の得点，英語の得点，合計点」 の組が受験者の数だけあり，それらを合計点の順に並べかえる， というような操作をすることが多いであろう。 これから考えるのは，（いわば）合計点だけを並べかえるもので， 実地にはあまり役立たない。 また，Excel （エクセル）などの表計算ソフトはソート機能を持っているので， 応用上はそれらを使えばよい。
(5.1.4) ※ 同じ値があった場合にどちらを先にもってくるかは， 「どちらでもよい」としておく。
実用上は，問題になる場合がある。 昔，試験のあと， 成績優秀者の氏名と得点を掲示したことがあった。 名簿の順に並んでいるデータを得点順に並べかえて上から何人かを選ぶのだが， もしも同点の学生がいた場合は左のように名簿の順にしておくのが普通である。
100 点 伊藤＊，田中＊＊，藤村＊＊ 100 点 藤村＊＊，伊藤＊，田中＊＊
95 点 ... 95 点 ...
そうではなく，右のように書いたとすると 「同じ 100 点だけど藤村君が先頭にきているのは何か理由があるのかな」 と思われるのでうまくないかもしれない。
(5.2.1) 次のプログラム例を見ながら， 以下の説明を読むこと。 また，このプログラムは完全ではないので， 指示に従って自分で書き加える必要がある。 長いので，コピペすることを強くすすめる。
#include <stdio.h>
#include <stdlib.h> /* rand(), srand() */
#include <time.h> /* time() */
#define N 10
void init(void);
void print(void);
int a[N+1]; /* これで a[1] ... a[N] が使える。a[0] は使わない */
main() {
printf("配列の大きさは %d です. ", N); /* 配列の大きさを出力 */
printf("…………田中美佐子\n", N); /* 自分の氏名を出力 */
init(); /* 初期化 */
print(); /* 画面表示 */
}
void init(void) {
int i;
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
printf("乱数の種は %u です.\n", seed);
srand(seed); /* それを乱数の種に */
}
a[0] = 0; /* 念のためこうしておく */
if (N < 70) { /* N が小さいとき */
/* ここを各自で埋めよ */
} else { /* N を大きくして実験するとき */
for (i = 1; i <= N; i++) {
a[i] = rand();
}
}
return; /* この return は普通は書かない */
}
void print(void) {
/* このコメントは消して，ここに関数 print() の本体を書く */
}
(5.2.2) 数列は，int 型の配列 a[ ] に入れる。 その大きさ N は， 容易に変えられるよう， #define を使って書いた。
(5.2.3) Ｃ言語の配列は添え字が 0 から始まるので，普通は a[0] から a[N-1] までを使うことになるが， わかりやすくするため a[1] から a[N] までを使いたい。 それには， 「int a[N+1];」と宣言することで a[0] から a[N] までを用意し， 最初の一つ，a[0] は使わなければよい。
(5.2.4) 初めに，init() という自作関数でこの配列を「初期化」する。 初期化とは，一般には初めのデータを代入することである。 ここでは乱数で初期化する。
(5.2.5) 「void init(void) {」で始まっているが， 最初の void はこの関数が値を返さないことを示す。 値は返さないがある働きをする，という関数である。 小カッコの中の void は，引数がないことを示す。 使うときは「init();」のように使う。 小カッコの中には何も書かない。 すでに出てきた，rand()がそうだった。
(5.2.6) N の値によって初期化を変える理由を， 以下で説明する。
(5.2.7) 考えながらプログラムを書いている間は，N の値を小さくとり， ソートの過程で何度か配列の値を全て出力して， ソートが進んでいることを確認する。 この段階では， 配列を初期化する際に代入する値は 100 未満で十分だし， そのほうが画面上での大小の比較が容易である。 また，あとで説明するが， これらの値は 1 以上としておくほうが， プログラムの間違いを見つけやすい。 以上から，値の範囲は 1 以上 99 以下としよう。
(5.2.8) プログラムが完成したら， N の値を何百万，何千万と大きくしての実験も行なう。 その際には， 同じ値で初期化された項がたくさんあるとうまくないので， 値の範囲は広ければ広いほどよい。 よって，配列には乱数の値をそのまま代入し， 値の範囲を 0 以上 RAND_MAX 以下とする。
(5.2.9) 上の init() の， 「N が小さいとき」の部分を各自で書け。
(5.2.10) プログラムの末尾にある関数 print() の本体を書け。 この関数は，配列に格納されている値を (5.1.1) に示したようなスタイルで， すなわち，スペースで区切って一行に出力し，最後に改行するものとする。 数が一桁のときも二桁分の幅に出力されるようにせよ。 そのとき，十の位を 0 とするかスペースにするかは各自の趣味にまかせる。 （printf() の中で， %d の代わりに %02d または %2d と書けばよい。）
(5.2.11) main() では init() と print() を続けて呼んでいるだけなので， 起動するたびに異なる乱数列が表示されるプログラムができたはずである。 （非常に短い間隔で起動すると，同じ乱数列になることもある。）
(5.2.12) ※ N を 70 にしてコンパイルすると， 出力はどうなるか？
(5.3.1) ソートプログラムの多くは， 互換， すなわち配列の二つの要素の交換からできている。 そこで，まず，互換を行なう関数を書こう。
(5.3.2) §5.2 で完成させたプログラムに， 関数 void swap(int i, int j) を書き加えよ。 この関数は， 要素 a[i] と a[j] の値を入れかえるものとする。 i と j が正しい範囲にあるかどうかはチェックしなくてよろしい。 そのことは，この関数を呼び出す際に注意するものとする。 プロトタイプ宣言もつけ加えること。 （最初は i と j とは等しくないと仮定して書いてみて， 書けたものが i と j が等しいときも正しく動くかどうか考えよ。）
(5.3.3) 次はダメな例である。
a[i] = a[j];
a[j] = a[i];
(5.3.4) この関数を呼び出してみなければ，正しく書けたかどうかはわからない。 それには，main() の最後に次のように付け加えればよいだろう。
swap(3, 8);
print();
これで a[3] と a[8] が入れかわっていれば OK である。 swap(8, 3) や swap(3, 3) も試すこと。
(5.3.5) ※ swap(-1, 8) や swap(3, N+1) を実行させるプログラムは， 配列の添え字が範囲外になるので誤ったプログラムである。 そのことを理解したうえで，そういうプログラムを書いて実行してみよ。 ここのコンピュータでは，エラーメッセージなどは出ない。 前者では a[8] に，後者では a[3] に， 配列の“外”にあった値がはいってくることになるが， それは 0 であることが多い。確かめよ。
(5.3.6) ※ これから書くプログラムは，少しずつ複雑になってゆく。 その際，間違って swap(-1, 8) や swap(3, N+1) を実行するようなプログラムを書いてしまうことはよくある。 配列を初期化する際，値の範囲を 1 から 99 までとしておいたのは， print() が 0 を出力したら間違いだとすぐにわかるためであった。 a[0] に 0 を代入しておいたのも同様の理由からである。
(5.4.1) 配列の要素 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) と書けば， スピードの点で若干劣るが，同じことである。 プロトタイプ宣言も付け足しておくこと。
(5.4.2) main() の最後に（swap() のテスト用に書いた部分は消してから） 次のように書き足して実験してみよう。
if (comp(1, 2) > 0) {
swap(1, 2);
}
print();
どうなれば実験成功かは各自で考えること。
(5.5.1) しばらくの間，プログラミングを離れて， ソートの「アルゴリズム」について考えてみよう。 「アルゴリズム」とは， 問題を解くための手順をあいまいさのないように書いたもののことである。
(5.5.2) ※ 配列の要素には等しい値をもつものがあるかも知れないが， その場合のことには深入りしないので，各自考えること。 また，添え字の範囲のうち，常識でわかるものは断らない。
(5.5.3) まずは，「素朴なソート」を考える。 これは特定のアルゴリズムの名前ではなく， プログラミングの経験を少し積んだ人がちょっと考えれば思いつくものを呼ぶ， 一般的な名前である。
(5.6.1) ソートのアルゴリズムの良し悪しは， 比較回数（＝配列の中の二つの要素を比較する回数）， 交換回数（＝配列の中の二つの要素の互換を行なう回数） を配列の大きさ N の関数とみなして判定する。 少ない回数で済むほうがよいアルゴリズムである。
(5.6.2) オーダーを表すオミクロン記法を復習しよう。 ここでは N→∞ のときだけを考える。 N の関数 f(N) と g(N) があって， 「N→∞ のとき |f(N)/g(N)| は有界」なら， f(N) = Ο(g(N)) と書き， 「f(N) のオーダーは g(N) のオーダー以下である」などと言う。 たとえば N(N-1)/2 = Ο(N2) である。
(5.6.3) アルゴリズムの良し悪しを論ずる際には， 必要な回数をデータの大きさ （ここでは配列の大きさ） N の関数とみなしたときのオーダーがまず第一に問題となる。 オーダーが同じ場合は係数が次の問題となる。 すなわち，同じ Ο(N2) であった場合には， N2/4 のほうが N2/2 よりも優れたアルゴリズムとなる。
(5.6.4) Ο(N log(N)) のアルゴリズムは Ο(N2) のアルゴリズムでもあるわけだが， わざわざ悪く言うこともないのでそれを 「Ο(N2) のアルゴリズム」と呼ぶことは滅多にない。
(5.6.5) 比較回数と交換回数とでオーダーが違うこともあるが， その場合は オーダーの大きいほうが全体のオーダーを決めることになる。 たとえば， Ο(N2) である関数 N2/2 と Ο(N) である関数 N とを足した N2/2 + N が Ο(N2) ではあるが Ο(N) ではないように。
(5.6.6) 興味のある人は，ソートのアルゴリズムをいくつか自分で考えてみよ。