プログラム電卓(Blockly)(5)
「プログラム電卓(Blockly)」の説明の続きです。各領域の番号は「ビジュアルプログラミング(14) - エレファント・コンピューティング調査報告」を参照してください。
「ソート1」の使い方
(11)のリストから「ソート1」を選択すると(12)の領域にサンプルのテキスト(JSON)が表示されます。その後(10)のボタンを押すと(2)の領域に「ソート1」のサンプルが表示されます。
- ボタン1 : (4)の領域の
と
に任意の自然数を指定して、(3)の「1」のボタンを押すと、(5)の領域に
から
- ボタン2 : (5)の領域を設定した後、(3)の「2」のボタンを押すと、選択ソートの一つの段階が実行され、(5)の領域の数が入れ替えられて、一つの数の位置が決まります(最初の数が最小の数になります)。この後「2」のボタンを押すごとに一つの数の位置が決まります(
回目でリストの
- ボタン3 : (5)の領域を設定した後、(3)の「3」のボタンを押すと、選択ソート実行され、(5)の領域がソートされます。
ボタン4からボタン7まではヒープソートを実行します。リストを以下のような木の構造と考えて、これを使ってソートを行います。
| 1 | 2 | 4 | 8 |
| 9 | |||
| 5 | 10 | ||
| 11 | |||
| 3 | 6 | 12 | |
| 13 | |||
| 7 | 14 | ||
| 15 |
- ボタン4 : (5)の領域がリストの
番目までがヒープとして降順のとき、(3)の「4」のボタンを押すと、リストの
番目までをヒープとして降順にします。
これを繰り返すと、リストの全体をヒープとして降順にすることができます。
- ボタン5 : (5)の領域がリストの
番目から
番目から
- ボタン6 : (5)の領域が設定されているとき、(3)の「6」のボタンを押すと、リストの
- ボタン7 : (5)の領域が設定されているとき、(3)の「7」のボタンを押すと、リストがソートされます。ボタン4を繰り返してリストの全体をヒープとして降順にした後、ボタン6、ボタン5を繰り返すと、リストの最後尾から順にそのときの最大値となり、最終的にはソートされます。これをヒープソートと呼びます。
- ボタン8 : (5)の領域が設定されているとき、(8)のチェックボックスをチェックして(3)の「8」のボタンを押すと、(6)の領域リストが上記の表のような構造として表示されます。たとえば
の場合
と表示されます。
は
が
「ソート2」の使い方
(11)のリストから「ソート2」を選択すると(12)の領域にサンプルのテキスト(JSON)が表示されます。その後(10)のボタンを押すと(2)の領域に「ソート2」のサンプルが表示されます。
- ボタン1 : (4)の領域の
- ボタン2 : (5)の領域を設定した後、(3)の「2」のボタンを押すと、ヒープソートが実行されます。「ソート1」のボタン7と同様ですが、関数を使って書いています。
- ボタン3 : (5)の領域を設定した後、(3)の「3」のボタンを押すと、クイックソートが実行されます。
リストの要素を、ある基準の数より小さいかまたは等しいものと、その基準の数より大きいものに分けて、リストの前半と後半にそれぞれまとめます。そしてその前半と後半に対して同じ操作を再帰的に行うことにより最後にはソートされます。この方法をクイックソートといいます。基準の数が最大値の場合はうまくいかないので、ここではリストの最初から一つずつ試してみてうまくいったものを採用するようにしています。
基準の数より小さいものと大きいものに分けて、基準の数は取り除く方法も考えられます。
