・交換と数字の発見の処理をつくろう

今回はアルゴリズムを学んでいくよ。 アルゴリズムとはコンピューターの計算方法のことだよ。 今回のレッスンでは、並べ替えのアルゴリズムを学んでみよう。

たくさんのデータが並ぶ、数字を小さい順に並べ変えるアルゴリズムを考えていくよ。 並べ替えには大きく2つの処理が必要だね。 １つ目は、数字を交換する処理 ２つ目は、交換すべき数字を見つける処理 調べるデータに乱数のリストを用意して、2つの方法で並べ替えを実行してみるよ。 2つの違いについては、これからレッスンで紹介していくから、今は気にしなくていいよ。 最終的に、小さい順に並べるだけだけど、その処理は何通りも考えられるよ。 その違いや良し悪しについてもレッスンの最後の方で学べるので、楽しみにしててね。 では、実際に作っていこう！

・背景・スプライトの設定を確認しよう

このチャプターでは、背景とスプライトの設定を確認していくよ。

「データの分析をしてみよう」で作った一部のブロックがすでにある状態から始めるよ。

• グリーンフラッグがクリックされたとき
• gキーが押されたとき
• 定義ブロック「読み込みデータを調べるデータへ」
• 「乱数のリストをつくる」

合計4つのブロックのかたまりが、確認できればOKだよ。 さあ！ここまで、みんなの画面でもやってみよう！

・交換する変数の置き場所を用意しよう

このチャプターでは、並べ替えに必要な数字の交換の処理を作っていくよ。 調べるデータの何番目と何番目を交換するかを指定できるように引数を含む定義ブロックをつくっていこう。

処理の流れについて説明するね。 scratchでは交換するというブロックはないよ。 実は、交換という処理は2つのことを同時におこなっているよね。 コンピューターは、順番が決まっていない作業は苦手なので、つぎのように処理をわけるよ。

例えば、6番目の数字と2番目の数字を交換するとしよう。

• 6番目の数字を変数「交換する数字」の値として保存しておく。
• 2番目の数字を6番目の数字に置き換える。
• 変数「交換する数字」の値を2番目の数字に置き換える。

2つのお皿の料理を入れ替えるために、3つのお皿を用意して、入れ替えるイメージだよ。

変数「交換する数字」をつくろう。 値は、これから交換される数字になるよ。 定義ブロック「数字の交換」をつくろう。 オプションをクリックして、引数を2個作ってね。 それぞれ、引数の名前は[x]、[y]としてね。

[x]番目の数字を、変数「交換する数字」に一時的に保存する処理をつくろう。

交換する数字を置き換える処理をつくろう。 [x]と[y]を間違えないようにしてね。 この処理は[y]番目の数字で[x]番目を置き換えてしまう処理だよ。

交換する数字の値で[y]番目の数字を置き換えよう。

ここまで完成したら、途中の動作確認をしてみよう。 [3秒待つ]は、動作が正しいか確認するために、一瞬いっしゅんで処理が実行されてしまわれないようにするためのブロックだよ。 リストがつくられて、10番目と9番目が交換されていればOKだよ。

さらに、ブロックを組み合わせて動作を確認しよう! 10番目の数字が交換されて、1番目にまで交換されていればOKだよ。

動作が正しいことが確認されたら、確認のためだけに作ったブロックを削除しておこう。 ここまで、みんなの画面でもやってみよう。

・変数を駆使くししてリストの値を並べ変えよう

このチャプターでは、並べ替えのアルゴリズムの基本である「バブルソート」という処理を作っていくね。 「バブル」は日本語で「泡」、「ソート」は「並べ替え」という意味だよ。 データが泡のように並べ変わっていくので、バブルソートという名前になったよ。

処理の流れについて、まずは、具体的に説明するね。 [9,4,5]というリストがあったとして、[4,5,9]と並べ替えをする手順について説明するね。

• データの最後から、つまり5と4を比べる。5は4より大きいからそのまま何もしない。
• 比べる場所をずらして、4と9を比べる。4は9より小さいから交換する。これで[4,9,5]になっているね。
• またデータの最後から、つまり5と9を比べる。5は9より小さいから交換する。

これで、[4,5,9]になっているね。

まず、「リストの何番目を調べるのか」を表す変数「調べ中」を作ろう。 並べ替えの処理が進むに連れて、小さい数が最初の方にあつまってくるため、比べる回数は減らしていった方が効率が良いよね。 まず、変数「比べる回数」をつくろう。 値は、データの最後から比べる回数となるよ。

定義ブロック「バブルソート」をつくろう。

比べる回数は、最初のデータ数マイナス1でいいね。 3個の数字の並べ替えだと、2回でいいことからも想像できるよね。

次に、データの調べる場所は、最後からでいいね。

データの長さによって、最後から調べるためには、データ数を調べる場所にしてあげよう。 比べる回数ぶんだけ繰り返す処理をつくろう。

具体的な処理は、最後から2つずつ数字を比べて小さいものを最初の方に交換していく処理だよ。 調べる場所をマイナス1ずつ替えながら、数字の交換をする処理をつくろう。

条件には、調べ中と調べ中の1つ手前の数字の値を比べる式が入るよ。 調べ中の値が調べ中の1つ手前の値より小さければという条件式をつくろう。

作った条件を追加して、動作確認のために[0.5秒待つ]処理をいれよう。 次に、乱数のリストの引数の値を変更しよう。 また、bキーを押した時にバブルソートがはじまるようにしておこう。

これまでつくった処理を繰り返すことで、全ての数字が並べ替えられていくね。 繰り返す回数は、データ数マイナス1回でいいよね。 10個のデータなら1回の処理で小さい数が泡のように上がっていくから、9回処理を繰り返すというイメージだよ。

最後に、比べる回数は、1回の繰り返し処理がおわる度に、並べかわっていくため、減らしていく方が効率こうりつがよかったね。

ここまで完成したら、動作を確認しよう。 rキーを押して、乱数のリストをつくり、bキーを押してバブルソートを実行しよう。 データの最後から比べる、交換の処理が繰り返されていること、比べる回数が減っていっていること、最後に小さい順に並べかわっていることを確認できればOKだよ。 ちなみに、比べている数字が同じ場合は、交換はされていないよ。 さあ！ここまで、みんなの画面でもやってみよう！

・最小値を発見して交換する処理を繰り返そう

このチャプターでは、並べ替えのアルゴリズムのもうひとつの基本である、「選択ソート」について学んでいくね。 処理の流れについて、まずは具体的に説明するね。

「バブルソート」のときと同様に、[9,4,5]というリストがあったとして、[4,5,9]と並べ替えをする手順について説明するね。

• 1番目の9に注目し、仮の最小値とする。
• 2番目の数字4と最小値を比べて、4の方が9より小さいので、最小値の場所が2番目と記録する。
• 3番目の数字5と最小値を比べて、5の方が小さくないので、何もしない。
• 全ての最小値が2番目と分かったので、1番目の9と2番目の4を交換する。

これで、[4,9,5]となったね。

• 1番目の数字が最小値だと分かったので、2番目の9を仮の最小値とする。
• 3番目の数字5と最小値を比べて、5の方が9より小さいので、最小値の場所が3番目と記録する。
• 2番目の数字9と3番目の数字5を交換する。

変数「注目する数字の場所」をつくろう。 値は、データが並べられかわっていくにつれて、仮の最小値とする場所が2番目、3番目と、かわっていくので、最初が1で1ずつ増えていくよ。

注目する場所、つまり仮の最小値は、リストを調べるたびに更新されていくね。 最小値が最初の方に集まってくる度に更新される変数「最小値の場所」を作ろう！

定義ブロック「選択ソート」をつくろう！

比べる回数は、最初はデータの数マイナス1でいいね。

並べ替えが進むごとに、比べる回数は減っていくよ。 注目する場所、つまり仮の最小値は1番目としておこう。

並べ替えが進むごとに、注目する数字の場所は1つずつずれていくね。 仮の最小値の場所は、毎回の繰り返しで注目する場所に変更されていくね。

毎回の並べ替えで、最小値を見つけていくときに調べる場所は注目する数字の場所の次、つまりプラス1番目にすればいいね。

仮の最小値がきまった上で、繰り返しの処理をつくって行こう処理の回数は比べる回数でいいね。

繰り返す処理をつくり、最後に交換する処理をつなげておこう。 これで、並べ替えがおわっていない数の最小値の場所がきまり、仮の最小値と見つかった最小値の数字を交換する処理ができたよ。

次に条件を考えていこう。 「仮の最小値より調べている場所が小さければ」を条件式とすればいいね。

条件式を追加して、繰り返す回数を決める処理を作ろう。 毎回の処理で、最小値が1つずつ見つかり並べ変わっていくため、繰り返しの回数はデータの数マイナス1回となるね。

注目する数字と比べる数字を繰り返しの度に変化させる処理を作り、動作確認のために[1秒待つ]をつなげておこう。 また、sキーを押したときに、選択ソートが実行されるようにしよう。

注目する数字の場所は最初1番目だけど、最小値がきまるたびに1ずつ変えればいいね。 また、比べる回数は最初はデータの数マイナス1だけど、最小値が決まるたびに、マイナス1ずつ変えていいね。 ここまで完成したら、動作を確認してみよう。 rキーを押して乱数のリストを作り、sキーを押して、選択ソートを実行しよう。 数字が上から順に比べられていること。 最小値が上から順にうまっっていき並べ変わっていくこと、最後に小さい順に並べかわっていることを確認できればOKだよ。 ここまで、みんなの画面でもやってみよう！

・処理時間を計測する処理をつくろう

このチャプターでは、作った2つの処理「バブルソート」と「選択ソート」の処理の速さを比較していくよ。

コンピューターに処理をさせる数が多くなればなるほど、時間がかかるよ。 並べ替えするデータがすごく多くても、早く終わる処理はどちらだろう？ 処理にかかる時間を測ってみよう。 処理の流れについて説明するね。 同じ乱数のリストをバブルソートと選択ソートで並べ帰る時間を比較するよ。 rキーを押す度に乱数のリストがかわってしまうため、調べるデータに入った乱数のリストを読み込みリストに読み込ませて保存しておこう。 処理時間を測るために、変数「処理時間」を作ろう。

バブルソートの処理を遅らせるブロックは削除しておこう。

選択ソートの処理を遅らせるブロックも削除しておこう。

定義ブロック「調べるデータを読み込みデータへ」をつくろう。 すでに、「読み込みデータを調べるデータへ」があるので、複製して変更していこう。

変更は、調べるデータを読み込みデータに、読み込みデータを調べるデータに変更していけばいいよ。

cキーが押された時に、調べるデータが読み込みデータにコピーされるようにしよう。

処理時間を測るためには、ソートの処理それぞれの直前にタイマーをリセットボタン、ソートの処理それぞれの直後に処理時間をタイマーにするという処理を作ればいいね。

乱数のリストの長さを1000に変更しよう。 途中の動作確認をしてみよう。

rキーを押すと、1000個の数字が調べるデータに入っていくね。 とても時間がかかってしまうため一度止めよう。 乱数のリストは1000個の数字としてみるため、ターボモードをつかってみるよ。 Shiftボタンを押しながらグリーンフラッグをクリックすることで、オンとオフを切り替えられるよ。 動作確認をしてみよう。 ターボモードになっていること、「処理時間」「調べるデータ」「読み込みデータ」が表示されていることを確認してから動作確認をしてね。 rキーを押して乱数のリストをつくろう。

cキーを押して、読み込みデータに乱数のリストを複製しよう。 準備が整ったら、bキーを押して、バブルソートを実行しよう。 続けて、gキーで読み込みデータを調べるデータへ移し、sキーを押して、選択ソートを実行させよう。 同じ並べ替えでも選択ソートの方がバブルソートの半分くらいの処理時間になることが分かったね！ ここまで、みんなの画面でもやってみよう！

・まとめ

このレッスンで、データの並べ替えの方法が１つではないことが分かってくれたかな？ プログラミング全体で言えることだけど、結果が同じでもその処理は何通りも考えることができるんだ。 そして、その処理の良し悪しは例えば時間で評価したりするんだ。 おさらいしておこう。

まず、リストの数字を交換する処理を考えたね。 仮の数字の置き場所として、交換する数字という変数をつくったことがポイントだね。 バブルソートでは、2つずつ値の大きさを比べて、なんども交換をすることで、小さい数を1番目、2番目と確定させていったね。 選択ソートでは、仮の最小値と、並べ替えがおわっていない数字を全て比べて、最小値を交換していくことで、小さい順に数字を確定させていくことができたね。 つまり、選択ソートの方が、交換の回数が少なく、処理にかかる時間が短くなっっているということだったんだ。

並べ替えには、他にもたくさんのアルゴリズムがあるから、気になる場合は自分でも 調べて、処理を作ってみよう。 scratchでもたくさんの人が、色々なソートを作っているよ。 プログラミングで何かアプリをつくる場合、処理の方法には時間や途中で得るデータによってどの方法を取るべきか考えることが重要だよ。 今回は並べ替えのアルゴリズムを取り扱ったけど、興味があれば、 他のアルゴリズムも勉強して、どんどんプログラミングの世界を楽しめるようになっていこう。 さあ！ここまで、みんなの画面でもやってみよう！