2010 年度「計算数学」 2010-12-17

§43 ソートの安定性

(43.1) この節は、課題が早く終わって時間が余った人のためのものである。 前に (25.4) で述べた、 ソート前のデータに同じ値があった場合の問題を考えよう。

(43.2) あるソートのアルゴリズムが「安定 (stable)」であるとは、 同じ値のものが、ソート後も元の順序を保っていることをいう。 あるソートアルゴリズムが安定であることは、 数学の命題のように証明して示すべきであり、 不安定（あるいは非安定）であることは、反例をもって示すべきであるが、 実験で試し、その結果を参考にすることができる。

(43.3) この授業で書いているプログラムでも、少し改変することで、 この実験が行なえる。以下では、そのやり方の一つを説明する。 まず、この授業でとりあげているスタイルで、 あるソートのプログラムが書けたとする。 そのソースファイルのコピーを、次のように改変しよう。

• int a[N+1]; の次の行に int b[N+1]; を追加する。 （i.e. 同じ長さの配列をもう一つ用意する。）
• 配列を初期化する関数 init() は、 a[i] はいままで通りに乱数で初期化するが、 b[i] には i を代入して初期化する。
• 配列を画面に出力する関数 print() は、 a[i] の値を一行に出力したのち、 b[i] の値を次の行に出力する。 （ヒープソートの場合もこのまま使う。）
• 互換を行なう関数 swap() は、 swap(i, j) を実行したとき、 a[i] と a[j] の値を入れ換えるだけでなく、 b[i] と b[j] の値も入れ換える。

(43.5) N の大きさを画面の一行に収まるぐらいとし、 途中の過程をすべて出力させて実験すれば、 どの過程で安定性が崩れるのかをも見ることができる。

(43.6) 配列の大きさを大きくして試したい場合、 安定かどうかを目で見て判定するのは大変であろう。 print() は呼ばないようにし、 main() の最後に安定かどうかをチェックする部分をつけるとよい。

ヒープソートのプログラムを書く際の補足（(42.5) に関連）

第一段は downheap(i, N) を実行するが、このとき、 第二の引数は N で、一定である。 少なくとも、N が偶数の場合と奇数の場合の両方で、 downheap() が正しく書けているかどうかチェックする。 左の子しかいない場合が発生するための条件は N が偶数であることだから。

次に第二段を書くときには downheap() は正しく書けていると信じることにする。よって、 downheap() の中での print() の呼び出しはコメントとし、 swap(1, i) を実行した直後と、 downheap() を呼んだ直後にだけ print() を実行する。 こうしておくと、 第二段の出力量が減るので、追いかけやすくなるはずである。 特に、どこから先が確定しているのかでわからなくなることが減ると思う。