配列(リスト)を使った数値データの扱いを学習する。
適当な数を配列にいれて練習用のデータを作る。 あまりたくさんのデータがあると動作の検証がやりにくいのでとりあえず5つぐらいで試してみる。
配列の値を順番に調べていって、最大値を探す。 順番に調べるためには適当な変数(ここではn)をつくって、その値を順に変化させていく。
n-1番目までを探したなかで最も大きな値をmaxとしておく。 n番目とmaxを比較してn番目のほうが大きいときにmaxにその値を設定する。
繰り返しの条件の作り方に気を付けること。 Scratchの配列(リスト)では最初が1で、最後が配列の個数になる。 ○まで繰り返すは、その条件が成立したときに実行されないことに注意する。 配列の最後まで繰り返させるには「配列の長さより大きい」まで繰り返すようにする。
m番目とn番目を入れ替えるプログラムは以下のようになる。 入れ替えのために一次的に値を退避させる変数の名前にはよくbuf(buffer)とかtmp(temporary)が使われる。
n番目とn+1番目を入れ替えるプログラムに書き換えてみる。 繰り返しの条件に注意して、なぜそうなっているのかを考えること。
Scratchの比較には「以上」とか「以下」がないので、「値の長さ-1より大きい」にしている。 多くのプログラミング言語には>=とか<=とかがあって、そういうときは n >= 値の長さ とする。
このプログラムを実行すると値の並び順がどう変わるのか考え、それを確認すること。
n番目がn+1番目より大きいときだけ入れ替えるように変更する。 このプログラムを繰り返し実行すると値の並び順がどう変わるのか調べよ。
ある値のまとまりを並び替えることをソート(sort)という。 コンピュータで並び替えを行うには様々な方法があるが、今回はその仕組みを理解しやすいバブルソートを実装してみる。 バブルソートのしくみ(アルゴリズム)はWikipediaを参照すること。
上記の練習の入れ替えプログラムを実行すると、最初の1回で一番大きい値が配列の最後に入れられることがわかる。 これを配列の回数だけ繰り返せば並び替えができることがわかったと思う。
値の比較と入れ替えはそれなりにコンピュータの計算能力を使うことであり、データ数が増えると時間がかかる。 特に上記のように行うと配列の個数の2乗に比例した時間がかかる。
計算時間を減らすための工夫として、並び替えが終わった部分については実行しないことが考えられる。 上記の例では(例えばデータ数が5のとき)、1回目の入れ替えでは5番目まで比較をしないといけないが、その次では4番目まででいい(すでに5番目には最も大きいものがあることがわかっているから)。 つまり、2重ループの内側では繰り返しの数が順番に減っていくことになる。
配列(リスト)の値を降順に(大から小へ)並び替えるプログラムを作成せよ。 作成したプログラムを提出すること(スクリーンショットではないことに注意する)。