整列

整列とは

データをある規則に従って並べ替えることです。コンピューターの用語では英語で「ソート」とよばれます。ある規則とは数値の大きさの順や文字列のABC順などをさします。

多量のデータを整理するのに欠かせない機能ですからより多くのデータをより速く整列する方法が工夫されました。いまではすでにあるプログラムを利用させてもらうのが一般的です。しかし、整列はプログラミング基礎です。このプログラムの動作を考えることを通してプログラムへの理解が深まります。ぜひ自分がコンピュータになったつもりで考えてみてください。

同じことをするプログラムでも作り方により仕事が速かったり遅かったりします。どうすれば効率のよいプログラムになるかとアイディアをしぼることも大切です。プログラムは PRINT IF THEN FOR NEXT などの命令を覚えるだけではできません。いやむしろこのアイディアをしぼることがプログラムの中心だといえるのです。

コンピュータを使っての整列には選択ソート、バブルソート、挿入ソート、クイックソート、マージソートなどたくさんのやり方があります。コンピュータではこのやり方のことをアルゴリズムといいます。「算法」と訳されていますがあまりぴったりしません。ふつうアルゴリズムといっています。

まず選択ソートから学んでいきます。

選択ソート

すべてのデータの中から最も小さい(もしくは大きい)データを選択し,先頭のデータと入れ換える.次に,残りのデータに対して同じ処理を繰り返し,最後から2番目の場所に正しいデータが入ったとき,全体の並べ替えが完了する.このようなやり方を選択ソートといいます。

考え方

次のような数字で実際にやってみます。まず、1番〜10番の中で一番小さいのは12です。これを1番目の52と交換します。

 52  46  24  12  15  35  18  56  63  23 
 12  46  24  52  15  35  18  56  63  23 

1番目を固定し、2番〜10番の中で最小のものをさがします。それは15です。これを2番目の46と交換します。

 12  46  24  52  15  35  18  56  63  23 
 12  15  24  52  46  35  18  56  63  23 

2番目を固定し、3番〜10番の中で最小のものをさがします。それは18です。これを3番目の24と交換します。

 12  15  24  52  46  35  18  56  63  23 
 12  15  18  52  46  35  24  56  63  23 

3番目を固定し、4番〜10番の中で最小のものをさがします。それは24です。これを4番目の52と交換します。

 12  15  18  52  46  35  24  56  63  23 
 12  15  18  23  46  35  24  56  63  52 

これを最後まで繰り返します。最後は9番から10番の中から最小のものをさがし、9番目と交換することになります。9番目と交換するというのが最後になります。

 12  15  18  23  24  35  46  52  63  56 
 12  15  18  23  24  35  46  52  56  63 

プログラム例

上の考え方をプログラムにします。やりかたはいろいろあります。

配列の用意

数値を大きさの順に並べ替えて出力するプログラムを作ります。手始めに10個の数字を並び替えます。10個の数値はa(1)からa(10)までの配列にREAD文で代入します。

DATA 52,46,24,12,15,35,18,56,63,23
DIM a(10)
FOR i=1 TO 10
   READ a(i)
NEXT i

整列の本体部分

i=1 to 9 の i は選択範囲の先頭番号です。最初は1で、1番小さいのと交換したら次は2からというように、先頭番号は大きくなっていきます。最後は10でなくて9です。これは上の実際の例でみたように、10番から10番までで一番小さいのはと考える必要がないからです。

FOR i=1 TO 9
   a(i)からa(10)までのうちで最小のものを見つける
   見つけたものと、先頭 つまり a(i) と交換する
NEXT i

青い部分と緑の部分は後で詳しく考えます。

整列した結果の表示

FOR i=1 TO 10
   PRINT a(i);
NEXT i

最小を見つける部分

最小のものを見つける部分です。i は範囲の先頭番号、k は最小の要素の番号です。最初に LET k=i とあるのは、仮に先頭を最小としておくのです。次のFOR〜NEXTで、それより小さいものがあるとそれを採用するということをしています。

   LET k=i
   FOR j=i+1 TO 10
      IF a(j)<a(k) THEN LET k=j
   NEXT j

i=3 の時の様子です。

交換する部分

交換する部分です。 t という作業変数を使っています。a(k)が現在の範囲の中で一番小さい数字。a(i)が先頭のデータです。これを取り替えます。

   LET t=a(i) 
   LET a(i)=a(k)
   LET a(k)=t

例35

上記プログラムを完成させなさい。


聖愛高等学校
http://www.seiai.ed.jp/