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

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

バブルソート

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

プロジェクトの例

• Sorting Algorithm Animation
• Comparing Sorting Methods

関連項目

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