提供: Japanese Scratch-Wiki

2017年7月19日 (水) 16:11時点におけるKurankuran (トーク | 投稿記録)による版 (小見出しを前後に揃える)

このチュートリアルでは、リスト内の要素を、大きさ順に並び替える方法を説明する。ここで説明する並び替え (ソート) 方法は、それぞれバブルソート挿入ソートクイックソートと呼ばれている。

バブルソート

次にバブルソートのアルゴリズムをScratchで実装する例を示す。バブルソートは、数多くあるデータソート方法の一種である:

@ がクリックされたとき
[実行フラグ v] を [0] にする
[交換フラグ v] を [0] にする
<<(実行フラグ) > [0]> かつ <(交換フラグ) = [0]>> まで繰り返す
   [項目No v] を [0] にする
  [実行フラグ v] を (1) ずつ変える
  [交換フラグ v] を [0] にする
  (([データ v] の長さ::list) - (1)) 回繰り返す
     [項目No v] を (1) ずつ変える
    もし <(((項目No) + (1)) 番目([データ v])) < ((項目No) 番目([データ v]))> なら
      [待避用変数 v] を (((項目No) + (1)) 番目([データ v])) にする
      ((項目No) + (1)) 番目([データ v])を ((項目No) 番目([データ v])) で置き換える
      (項目No) 番目([データ v])を (待避用変数) で置き換える
      [交換フラグ v] を (1) ずつ変える
    end
  end
end

このスクリプトを実行すると、リスト「データ」の中身が昇順 (小→大) に並び替えられる。

スクリプトのしくみ

  • このスクリプトは、リスト 「データ」の中身を並び替える
  • 並び替えのときは、隣同士にあるデータを順番に比較していく。
  • 比較した結果、値の場所を入れ替える必要があるとき(大きいほうの数が前にあるとき)は、変数「待避用変数」に移動先の値をよけておき、そこに大きいほうの値を移動する。次に、大きいほうの値が元あった場所に、「待避用変数」によけておいた値を入れる。
  • これを、場所の入れ替えが必要なくなるまで (値の並び替えが完了するまで) つづける

挿入ソート

次に、挿入ソートのアルゴリズムをScratchで実装する例を示す:

@ がクリックされたとき
[項目No v] を [2] にする
<([データ v] の長さ::list) < (項目No)> まで繰り返す
  [挿入場所 v] を ((項目No) - (1)) にする
  <<((挿入場所) 番目([データ v])) < ((項目No) 番目([データ v]))> または <(挿入場所) < [1]>> まで繰り返す
    [挿入場所 v] を (-1) ずつ変える
  end
  ((項目No) 番目([データ v])) を ((挿入場所) + (1)) 番目に挿入する([データ v])
  ((項目No) + (1)) 番目を[データ v]から削除する
   [項目No v] を (1) ずつ変える
end

このスクリプトを実行すると、リスト「データ」の中身が昇順 (小→大) に並び替えられる。

スクリプトのしくみ

  • このスクリプトは、リスト 「データ」の中身を並び替える
  • このスクリプトでは、リストを大きく2つに分けて扱っている。
  • 1つめは、すでに並び替えが終わっている部分、2つめはこれから並び替える部分である。
  • 2つめの並び替えが終わっていない部分からデータを1つ取り出し、これを1つめの並び替えが終わっている部分の適切な場所に挿入している。
  • 取り出すデータがなくなったとき(2つめの部分がなくなったとき)には、リストのデータ全体が昇順 (小→大) に並び替えられている。

クイックソート

次にクイックソートのアルゴリズムをScratchで実装する例を示す。最悪の場合、クイックソートのスピードは、バブルソートや挿入ソートと同じくらいになるが、そのような場合はめったにない。通常は、クイックソートはこれらよりもずっと効率的である。クイックソートでは再帰を使用することに注意してほしい。

定義 クイックソート (_開始位置) (_終了位置)
もし<((_終了位置) - (_開始位置)) < [2]> なら
もし<<(_終了位置) > (_開始位置)> かつ <((_開始位置) 番目([データ v])) > ((_終了位置) 番目([データ v]))>> なら
[待避用変数 v] を ((_開始位置) 番目([データ v])) にする
(_開始位置) 番目([データ v])を ((_終了位置) 番目([データ v])) で置き換える
(_終了位置) 番目([データ v])を (待避用変数) で置き換える
end
[このスクリプト v] を止める
end
[a v] を (_開始位置) にする
[b v] を ((_終了位置) - (1)) にする
<<(a) < (b)> ではない> まで繰り返す
もし <((a) 番目([データ v])) < ((_終了位置) 番目([データ v]))> なら
[a v] を (1) ずつ変える
でなければ
もし<((b) 番目([データ v])) > ((_終了位置) 番目([データ v]))> なら
[b v] を (-1) ずつ変える
でなければ
[待避用変数 v] を ((a) 番目([データ v])) にする
(a) 番目([データ v])を ((b) 番目([データ v])) で置き換える
(b) 番目([データ v])を (待避用変数) で置き換える
end
end
end
もし<((a) 番目([データ v])) < ((_終了位置) 番目([データ v]))> なら
[a v] を (1) ずつ変える
end
[待避用変数 v] を ((a) 番目([データ v])) にする
(a) 番目([データ v])を ((_終了位置) 番目([データ v])) で置き換える
(_終了位置) 番目([データ v])を (待避用変数) で置き換える
クイックソート (_開始位置) ((a) - (1))
クイックソート ((a) + (1)) (_終了位置)

@ がクリックされたとき
クイックソート (1) ([データ v] の長さ::list)

スクリプトのしくみ

  • このスクリプトは、リスト 「データ」の中身を並び替える。
  • 大まかな処理は、次のとおり。
    • すべての項目を最後の項目と比較する (ここでは、わかりやすさを優先して最後の項目を使った。このような比較対象とする項目を「ピボット」と言う)。
    • 比較の結果、リストを2つの部分リストに分割する:1つは、ピボットよりも小さい数のリスト、もう1つは、ピボットよりも大きい数のリスト。
    • このようにしてできたサブリストを、さらにどんどん分割してより細かいサブリストにしていく。サブリストの項目数が、2以下になれば、分割は終了。
    • すべての分割が終わったとき、リストの並び替えも終了している。

プロジェクトの例

関連項目