データの並び替え (ソート)

このきじは ひらがなのページがありません。ごめんなさい。

(ひらがな記事について/ひらがなきじについて)

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

バブルソート

次にバブルソートのアルゴリズムを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以下になれば、分割は終了。
  • すべての分割が終わったとき、リストの並び替えも終了している。

プロジェクトの例

• Sorting Algorithm Animation
• Comparing Sorting Methods

関連項目

• 新しいリスト項目を自動的に正しい位置に入れる