並べ替え

Scratch プログラミング言語でも配列変数が使えることは以前に紹介した．配列に読み込んだデータを順番に比較して，大きい方を最大値という変数に代入し，すべてのデータと比較が終われば，最大値が求まるというプログラムであった．

折角比較するなら，ついでに大きい順あるいは小さい順に並べ替えたら最大値，最小値を同時に求めることができるということになる．データが置かれている場所（配列）を容器に例えると分かりやすい．大小比較の際に，別の「容器」を準備しておいて，比較する相手が大きい場合は自分は赤の容器に一時的に退避し，空いた容器に相手が移動した後，相手が入っていた空容器に自分が退避先の容器から移動すれば大きい順に並ぶことになる．この操作を順番にすべての組み合わせについて繰り返せば大きい順に並ぶことになる．

データが５個の場合，比較する相手は以下のとおり．

データ１ ２ ３ ４ ５

データ２ ３ ４ ５

データ３ ４ ５

データ４ ５

データ５ なし

自分自身の比較，重複比較を除くと組み合わせは（個数の二乗ー個数）の半分ですむ．

プログラムでもそのような構文にする．

実行結果

参考データ

多言語でプログラミング経験のある人のために十進BASICの例を示した．

途中結果の出力データから，比較前後における配列の値が変化する様子が理解できる．

DIM x(5)

FOR i=1 TO 5

   READ x(i)

NEXT i

PRINT"Input Data"

FOR i=1 TO 5

   print x(i);

NEXT i

PRINT

PRINT

FOR i=1 TO 4

   PRINT " i=";I;"x(i)=";x(i)

   FOR J=i+1 TO 5

      PRINT "before  j=" ;j,"x(i)=";x(i) ;"x(j)=";x(j)

      IF x(j)>X(i) THEN

         LET kari=x(i)

         LET x(i)=x(j)

         LET x(j)=kari

         PRINT  "       interchanged"

      END IF

      PRINT "after   j=" ;j,"x(i)=";x(i) ;"x(j)=";x(j)

   NEXT j

   REM PRINT

   PRINT   " Tocyu kekka";

   FOR  n=1 TO 5

      print x(n);

   NEXT n

   print

   PRINT

NEXT i

PRINT

PRINT" Output Data"

FOR i=1 TO 5

   print x(i);

NEXT i

DATA 2,5,4,1,3

END

Input Data

 2  5  4  1  3

 i= 1 x(i)= 2

before  j= 2            x(i)= 2 x(j)= 5

       interchanged

after   j= 2            x(i)= 5 x(j)= 2

before  j= 3            x(i)= 5 x(j)= 4

after   j= 3            x(i)= 5 x(j)= 4

before  j= 4            x(i)= 5 x(j)= 1

after   j= 4            x(i)= 5 x(j)= 1

before  j= 5            x(i)= 5 x(j)= 3

after   j= 5            x(i)= 5 x(j)= 3

 Tocyu kekka 5  2  4  1  3

 i= 2 x(i)= 2

before  j= 3            x(i)= 2 x(j)= 4

       interchanged

after   j= 3            x(i)= 4 x(j)= 2

before  j= 4            x(i)= 4 x(j)= 1

after   j= 4            x(i)= 4 x(j)= 1

before  j= 5            x(i)= 4 x(j)= 3

after   j= 5            x(i)= 4 x(j)= 3

 Tocyu kekka 5  4  2  1  3

 i= 3 x(i)= 2

before  j= 4            x(i)= 2 x(j)= 1

after   j= 4            x(i)= 2 x(j)= 1

before  j= 5            x(i)= 2 x(j)= 3

       interchanged

after   j= 5            x(i)= 3 x(j)= 2

 Tocyu kekka 5  4  3  1  2

 i= 4 x(i)= 1

before  j= 5            x(i)= 1 x(j)= 2

       interchanged

after   j= 5            x(i)= 2 x(j)= 1

 Tocyu kekka 5  4  3  2  1

 Output Data

 5  4  3  2  1