(34.1) この授業は、内容としては前学期の「計算機基礎論３Ｂ」の続きである。
(34.2) 計算機の使い方は前学期と同じなので、説明は省く。
(34.3) この授業の（いわゆる）ホームページは http://wwwedu.ipe.kanazawa-u.ac.jp/%7Ez08ect01/ の下にある。見て、ブックマークに追加しておくこと。 また、そこには、前学期の「計算機基礎論３Ｂ」のプリントも置いてある。
(34.4) ブラウザ mozilla で複数のページを同時に見るには、 「ファイル」「新規作成」「Navigator ウィンドウ」とするか、 「ファイル」「新規作成」「Navigator タブ」とする。
(34.5) テキストエディタ emacs の設定のため、 「cp ~z08ect01/.em* .」 を一度だけ実行せよ。 「ディレクトリは対象外です」という警告メッセージが出るが、気にしなくてよい。
(34.6) メールアドレスは z08ec0??@mailedu.ipe.kanazawa-u.ac.jp となる。 §11 にならって Active! mail の設定を行なえ。 担当者（岩瀬）のアドレスは z08ect01@... である。
(35.1) この授業のテーマは「整列」、すなわち、
88 98 20 82 31 53 22 10 12 91 92 79 95 50 19 58のような有限数列が与えられたとき、 これを小さい順に並べかえることである。 「ソート (sort)」とも言う。 ただし、 「整列」「sort」の日常用語としての意味はこれとは少し違う。
(35.2) 次のプログラムを元に、 順次、書き足したり改良したりしてゆくが、 ソースファイル名は指定しないので、適当に決めよ。 ファイル名をプリントにメモしておくと、 あとで探すときに楽かも知れない。
(35.3) ※ 実際の仕事でコンピュータを使う際には、 数だけを並べかえたのでは意味がないのが普通である。 たとえば、 受験者一人一人に対応するデータ 「受験番号、国語の得点、数学の得点、英語の得点、合計点」 の組が受験者の数だけあり、それらを合計点の順に並べかえる、 というような操作をすることが多いであろう。 これから考えるのは、（いわば）合計点だけを並べかえるもので、 実地にはあまり役立たない。 また、Excel （エクセル）などの表計算ソフトはソート機能を持っているので、 応用上はそれらを使えばよい。
(35.4) ※ 同じ値があった場合にどちらを先にもってくるかは、 この授業では「どちらでもよい」としておく。 （実用上は、それも問題になることがある。 たとえば、昔は、試験のあと、 成績優秀者の氏名と得点を掲示したことがあった。 それには、 元々は名簿の順に並んでいるデータを得点順に並べかえて上から何人かを選べばよいのだが、 もしも同点の学生がいた場合は
100 点 伊藤＊、田中＊＊、藤村＊＊
95 点 ...
のように名簿の順にしておくのが普通である。
これを
100 点 藤村＊＊、伊藤＊、田中＊＊
95 点 ...
とすると
「同じ 100 点だけど藤村君が先頭にきているのは何か理由があるのかな」
と思われるのでうまくないかもしれない。）
(36.1) 次のプログラム例を見ながら、 以下の説明を読むこと。 また、このプログラムは完全ではないので、 指示に従って自分で書き加える必要がある。
#include <stdio.h>
#include <stdlib.h> /* srand() */
#include <time.h> /* time() */
#define N 20
void init(void);
void print(void);
int a[N+1]; /* これで a[1] ... a[N] が使える。a[0] は使わない */
main() {
init(); /* 初期化 */
print(); /* 画面表示 */
}
void init(void) {
int i;
{ /* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
printf("乱数の種は %u です.\n", seed);
srand(seed); /* それを乱数の種に */
}
a[0] = 0; /* 念のためこうしておく */
for (i = 1; i <= N; i++) {
a[i] = rand() % 99 + 1; /* N が小さいとき */
/* a[i] = rand(); /* N を大きくして実験するとき */
}
return; /* この return は普通は書かない */
}
void print(void) {
/* このコメントは消して、ここに関数 print() の本体を書く */
}
(36.2) 数列は、int 型の配列 a[ ] に入れることにした。 その大きさ N は、 容易に変えられるよう、 #define を使って書いた。
(36.3) Ｃ言語の配列は添字が 0 から始まるので、普通は a[0] から a[N-1] までを使うことになるが、 ここではわかりやすくするため a[1] から a[N] までを使いたい。 それには、 「int a[N+1];」と宣言することで a[0] から a[N] までを用意し、 最初の一つ、a[0] は使わなければよい。
(36.4) 初めに、この配列を「初期化」する。 「初期化」とは、一般には初めのデータを代入することである。 ここでは乱数で初期化する。 この部分は関数 init() として独立させた。
(36.5) void については §30 を、 rand(), srand() については §26 を参照。
(36.6) 「a[i] = ...」という行が二つ並んでいる理由について、 以下で説明する。
(36.7) プログラムを書いている間は、N の値を小さくとり、 ソートの過程の途中で、 何度か配列の値を全て出力してソートが進んでいることを確認する。 この段階では、 配列を初期化する値は 100 未満で十分だし、 そのほうが大小の比較が容易である。 また、あとで説明するが、 これらの値は 1 以上としておくほうが、 プログラムの間違いを見つけやすい。 以上から、値の範囲は 1 以上 99 以下としよう。
(36.8) プログラムが完成したら、 N の値を何百万、何千万と大きくしての実験も行なう。 その際には、 同じ値が代入されている項がたくさんあるとうまくないので、 値の範囲は広ければ広いほどよい。 よって、配列には乱数の値をそのまま代入する。 そこで、値の範囲は 0 以上 RAND_MAX 以下となる。 （RAND_MAX については §26 を参照。）
(36.9) そのため、init() の中には「a[i] = ...」 となっている行が二つあるのであった。 いまどの段階の作業をしているかに応じて、 一方を選び、他方はコメントとする。 すなわち、/* と */ とで囲む。
(36.10) プログラムの末尾にある関数 void print(void) の本体を書け。 この関数は、配列に格納されている値を (35.1) に示したようなスタイルで、 すなわち、スペースで区切って一行に、出力するものとする。 数が一桁のときも二桁分の幅に出力されるようにせよ。 そのとき、十の位を 0 とするかスペースにするかは各自の趣味にまかせる。 （printf() の中で、 %d の代わりに %02d または %2d と書けばよい。）
(36.11) これで上のプログラムはコンパイル可能になった。 main() では init() と print() を続けて呼んでいるだけなので、 起動するたびに異なる乱数列が表示されるプログラムができたはずである。 （非常に短い間隔で起動すると、同じ乱数列になることもある。）
(36.12) ※ init() の 「a[i] = ...」 のもう一方を使うと出力はどうなるか？
(37.1) ソートプログラムの多くは、 互換、 すなわち配列の二つの要素の交換からできている。 そこで、まず、互換を行なう関数を書こう。
(37.2) §36 で完成させたプログラムに、 関数 void swap(int i, int j) を書き加えよ。 この関数は、 要素 a[i] と a[j] の値を入れかえるものとする。 i と j が範囲内にあるかどうかはチェックしなくてよろしい。 プロトタイプ宣言もつけ加えること。
(37.3) ヒント：
a[i] = a[j];
a[j] = a[i];
ではだめである。
最初は i と j とは等しくないと仮定して書いてみて、
書けたものが i と j が等しいときも正しく動くかどうか考えよ。
(37.4) もちろん、 この関数を呼び出してみなければ、正しく書けたかどうかはわからない。 それには、main() の最後に
swap(3, 8);
print();
のように付け加えればよいだろう。
これで a[3] と a[8] が入れかわっていれば OK である。
ほかに swap(8, 3) や swap(3, 3) も試すこと。
(37.5) ※ swap(-1, 8) や swap(3, N+1) を実行させるプログラムは、 配列の添字が範囲外になるので誤ったプログラムである。 そのことを理解したうえで、そういうプログラムを書いて実行してみよ。 おそらく、ここのコンピュータでは、エラーメッセージなどは出ないであろう。 前者では a[8] に、後者では a[3] に、 配列の“外”にあった値がはいってくることになるが、 それは 0 であることが多い。確かめよ。
(37.6) ※ これから書くプログラムは、少しずつ複雑になってゆく。 その際、間違って swap(-1, 8) や swap(3, N+1) を実行するようなプログラムを書いてしまうことはよくある。 配列を初期化する際、値の範囲を 1 から 99 までとしておいたのは、 print() が 0 を出力したら間違いだとすぐにわかるためであった。 a[0] に 0 を代入しておいたのも同様の理由からである。
(38.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) と書けば同じことである。
プロトタイプ宣言も付け足しておくこと。
(38.2) main() の最後に
if (comp(1, 2) > 0) {
swap(1, 2);
}
print();
と書き足して実験してみよう。
どうなれば実験成功かは各自で考えること。