エレファント・コンピューティング調査報告

極限に関する順序を論理プログラミングの手法を使って指定することを目指すブロクです。

ビジュアルプログラミング(17)

プログラム電卓(Blockly)(5)

プログラム電卓(Blockly)」の説明の続きです。各領域の番号は「ビジュアルプログラミング(14) - エレファント・コンピューティング調査報告」を参照してください。

「ソート1」の使い方

(11)のリストから「ソート1」を選択すると(12)の領域にサンプルのテキスト(JSON)が表示されます。その後(10)のボタンを押すと(2)の領域に「ソート1」のサンプルが表示されます。

  • ボタン1 : (4)の領域の  x y に任意の自然数を指定して、(3)の「1」のボタンを押すと、(5)の領域に  1 から  y までのランダムな整数が  x 個表示されます。
  • ボタン2 : (5)の領域を設定した後、(3)の「2」のボタンを押すと、選択ソートの一つの段階が実行され、(5)の領域の数が入れ替えられて、一つの数の位置が決まります(最初の数が最小の数になります)。この後「2」のボタンを押すごとに一つの数の位置が決まります( n 回目でリストの  n 番目の要素が残りの数の中の最小の数となります)。
  • ボタン3 : (5)の領域を設定した後、(3)の「3」のボタンを押すと、選択ソート実行され、(5)の領域がソートされます。

ボタン4からボタン7まではヒープソートを実行します。リストを以下のような木の構造と考えて、これを使ってソートを行います。

1248
9
510
11
3612
13
714
15
この図の番号はリストの何番目の要素かを表します。同じ行の右隣は「子」となります。例えば2番目と3番目の要素は1番目の要素の「子」です。同じ行の左隣は「親」となります。例えば1番目の要素は2番目と3番目の要素の「親」です。任意の要素がその「親」に等しいか、その「親」より小さいとき、ヒープとして降順ということにします。

  • ボタン4 : (5)の領域がリストの  c - 1 番目までがヒープとして降順のとき、(3)の「4」のボタンを押すと、リストの  c 番目までをヒープとして降順にします。

これを繰り返すと、リストの全体をヒープとして降順にすることができます。

  • ボタン5 : (5)の領域がリストの  a + 1 番目から  c 番目までが降順のとき、(3)の「5」のボタンを押すと、リストの  a 番目から  c 番目までを降順にします。
  • ボタン6 : (5)の領域が設定されているとき、(3)の「6」のボタンを押すと、リストの  1 番目と  c 番目を入れ替えます。
  • ボタン7 : (5)の領域が設定されているとき、(3)の「7」のボタンを押すと、リストがソートされます。ボタン4を繰り返してリストの全体をヒープとして降順にした後、ボタン6、ボタン5を繰り返すと、リストの最後尾から順にそのときの最大値となり、最終的にはソートされます。これをヒープソートと呼びます。
  • ボタン8 : (5)の領域が設定されているとき、(8)チェックボックスをチェックして(3)の「8」のボタンを押すと、(6)の領域リストが上記の表のような構造として表示されます。たとえば  49,18,54,30,55,89,73,84,74,72 の場合  [49,[18,[30,[84],[74]],[55,[72]]],[54,[89],[73]]] と表示されます。 [x, y, z]  y z x の「子」であることを表します。

「ソート2」の使い方

(11)のリストから「ソート2」を選択すると(12)の領域にサンプルのテキスト(JSON)が表示されます。その後(10)のボタンを押すと(2)の領域に「ソート2」のサンプルが表示されます。

  • ボタン1 : (4)の領域の  x y に任意の自然数を指定して、(3)の「1」のボタンを押すと、(5)の領域に  1 から  y までのランダムな整数が  x 個表示されます。
  • ボタン2 : (5)の領域を設定した後、(3)の「2」のボタンを押すと、ヒープソートが実行されます。「ソート1」のボタン7と同様ですが、関数を使って書いています。
  • ボタン3 : (5)の領域を設定した後、(3)の「3」のボタンを押すと、クイックソートが実行されます。

リストの要素を、ある基準の数より小さいかまたは等しいものと、その基準の数より大きいものに分けて、リストの前半と後半にそれぞれまとめます。そしてその前半と後半に対して同じ操作を再帰的に行うことにより最後にはソートされます。この方法をクイックソートといいます。基準の数が最大値の場合はうまくいかないので、ここではリストの最初から一つずつ試してみてうまくいったものを採用するようにしています。

基準の数より小さいものと大きいものに分けて、基準の数は取り除く方法も考えられます。