(43.1) この節は、課題が早く終わって時間が余った人のためのものである。 前に (25.4) で述べた、 ソート前のデータに同じ値があった場合の問題である。
(43.2) あるソートのアルゴリズムが「安定 (stable)」であるとは、 最初にどんなデータが与えられても、 同じ値のデータが、ソート後に元の順序を保っていることをいう。
(43.3) あるソートアルゴリズムが安定であることは、 数学の命題のように証明して示すべきであり、 不安定（あるいは非安定）であることは、反例を示して証明すべきであるが、 実験で試し、その結果を参考にすることができる。
(43.4) この授業で書いているプログラムでも、少し改変することで、 この実験が行なえる。以下では、そのやり方の一つを説明する。
(43.5) まず、この授業でとりあげているスタイルで、 あるソートのプログラムが書けたとする。 そのソースファイルのコピーを、次のように改変しよう。
(43.6) 配列を初期化する関数 init() を、次のように改変する。 a[i] たちは、十個ずつまとめて初期化する。 具体的に言うと、 まず、三桁以下の自然数 x を一つ、乱数で決める。 a[1], a[2], ..., a[10] は、 それぞれ、10*x+0, 10*x+1, ..., 10*x+9 で初期化する。 次に、新たに三桁以下の自然数 x を一つ、乱数で決め、 a[11], a[12], ..., a[20] は それぞれ、10*x+0, 10*x+1, ..., 10*x+9 で初期化する。 以下、同様である。
(43.7) こうやって配列を四桁以下の整数で初期化するが、 ソートの際に比べるのは、一の位を除いた、上の（高々）三桁の値、とする。 そうやってソートしたあと、一の位が元の通り、 0, 1, 2, ..., 9 の順序になっているかどうかを見れば、 安定かどうかがわかる。 （厳密に言えば、安定かどうか考える際の参考になる、にすぎないが。）
(43.8) 元のプログラムが、 main() の最後で正しくソートが完了したかどうか確かめるようになっていれば、 その出力結果も参考になる。 （どう参考になるのかは、各自で考えること。）
(43.9) 配列を画面に出力する関数 print() は、 配列に格納されている値を、常に四桁の幅で、一行に出力するように改変する。 なお、ヒープソートについて実験するときも、 これをそのまま使う。
(43.10) 配列の二つの要素を比較する関数 int comp(int i, int j) は、 配列に格納されている二つの値を、一の位を無視して比較した結果を返す。 すなわち、a[i] が 3725, a[j] が 3723 の場合、 0 を返す。 そのように改変する。
(43.11) main() では、初期化直後と、ソート終了後の二回、 関数 print() を呼んで、配列の値を画面に出力する。
(43.12) 配列の大きさ N は 1000 ぐらいでよいと思う。 10, 20, 30 ぐらいで、途中の過程をすべて出力させて実験すれば、 どの過程で安定性が崩れるのかを見ることもできる。
(43.13) 上三桁を乱数で決める際、同じものが二度以上でてくることもある。 その場合の実験結果は適宜解釈すること。