提供: Japanese Scratch-Wiki

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.
このきじは ひらがなのページがありません。ごめんなさい。

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

バブルソート

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

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

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

スクリプトのしくみ

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

挿入ソート

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

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

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

スクリプトのしくみ

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

クイックソート

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

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

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

スクリプトのしくみ

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

プロジェクトの例

関連項目

Cookieは私達のサービスを提供するのに役立ちます。このサービスを使用することにより、お客様はCookieの使用に同意するものとします。