配列を大きい順番に並べ替える


いよいよ、「サンプルプログラムとその解説その1」の最後のサンプルプログラムです。今回は、サンプルプログラム 11 を使って、配列の要素を大きい順に並べ替えるプログラムを作ります。サンプルプログラム 11 では、配列 d の一番大きな要素が 1 番目の要素 d(1) へ来るように、配列 d を並べ替えました。プログラムが終了した時には、d(1) は配列の一番大きな要素ですが、d(2) > d(3) > d(4) > ... > d(n) が成り立っている保証はありません。そこで、サンプルプログラム 11 を使って d(1) を一番大きな要素にした後に、d(2), d(3), ..., d(n) に対して同様にサンプルプログラム 11 を使って、d(2) を d(2), d(3), ..., d(n) の中で一番大きな要素にします。そうすると d(1) > d(2) > d(3), d(4), ...., d(n) が成り立ちます。以下同様に、d(j),d(j+1),....,d(n) に対してサンプルプログラム 11 を使って、d(j) を d(j), d(j+1), ..., d(n) の中で一番大きな要素にするといった操作を j=1 から j=n-1 まで繰り返せば、プログラムが終了した時に d(1) > d(2) > d(3) > ... > d(n) が成り立っていることになります。以上のことを行うプログラムは以下のようになります。

サンプルプログラム12

プログラムの解説をします。

解説を読んだだけでは分かり難いかもしれません。実際にプログラムを動かしてみましょう。データの数として n=3、データとして -1, 4, 6 を入力すると、次のように並べ替えられたはずです。

この時のプログラムの実行過程を表の形で表します。ただし、表の各列は次の物を意味しています。

参照番号 行番号 d(i) i j n
1 10 ?, ?, ? ? ? 3
2 20 ?, ?, ? ? ? 3
3 30 ?, ?, ? 1 ? 3
4 40 -1, ?, ? 1 ? 3
5 50 -1, ?, ? 1 ? 3
6 30 -1, ?, ? 2 ? 3
7 40 -1, 4, ? 2 ? 3
8 50 -1, 4, ? 2 ? 3
9 30 -1, 4, ? 3 ? 3
10 40 -1, 4, 6 3 ? 3
11 50 -1, 4, 6 3 ? 3
12 60 -1, 4, 6 3 1 3
13 70 -1, 4, 6 2 1 3
14 80 4, -1, 6 2 1 3
15 90 4, -1, 6 2 1 3
16 70 4, -1, 6 3 1 3
17 80 6, -1, 4 3 1 3
18 90 6, -1, 4 3 1 3
19 100 6, -1, 4 3 1 3
20 60 6, -1, 4 3 2 3
21 70 6, -1, 4 3 2 3
22 80 6, 4, -1 3 2 3
23 90 6, 4, -1 3 2 3
24 100 6, 4, -1 3 2 3
25 110 6, 4, -1 1 2 3
26 120 6, 4, -1 1 2 3
27 130 6, 4, -1 1 2 3
28 110 6, 4, -1 2 2 3
29 120 6, 4, -1 2 2 3
30 130 6, 4, -1 2 2 3
31 110 6, 4, -1 3 2 3
32 120 6, 4, -1 3 2 3
33 130 6, 4, -1 3 2 3
34 140 6, 4, -1 3 2 3

プログラムの動作が良く分からない時は、上の表にしたがって、プログラムの実行過程を1つ1つ追ってみてください。配列 d(i) の値の交換が参照番号 14, 17, 22 で行われています。

このようにデータの並べ替えを行うやり方は、古くから様々なやり方が研究されて来ています。上のプログラムは複雑で分かり難いと思ったかもしれませんが、このやり方は最も単純なものの一つです。通常は、もっと効率的で洗練されたやり方で並べ替えが行われます。