目次(まとめ)
◾️ 交換ソートでは、隣り合う数字を比較して "交換" を繰り返す
◾️ 選択ソートでは、整列対象の数字の中から最小値/最大値を "選択" する操作を繰り返す
◾️ 挿入ソートでは、整列済みの配列の適切な場所に数字を "挿入" する操作を繰り返す
◾️ 参考文献
◾️ 関連記事
こんにちは、みっちゃんです。
今回の記事では、データを並び替える基本的な方法の仕組みを紹介します。
ここでは、例えば、以下のような数字の配列が与えられているとして、昇順(小さいものから順)に並び替える(ソートする)方法を考えます。
5 | 6 | 2 | 9 | 4 | 5 | 1 | 4 | 10 | 3 |
交換ソートでは、隣り合う数字を比較して "交換" を繰り返す
交換ソート(昇順)では、隣り合う数字を比較して、右側の数字が左側の数字より小さければ "交換" していきます。
❶上に示している数字の配列のうち、左から1番目の2番目にある数字("5" と "6")に注目して、右側が大きくなるようにする。この場合には、このままで大丈夫です。
❷左から2番目の3番目にある数字("6" と "2")に注目して、右側が大きくなるようにする。この場合には、右側の方が小さい数字になっているので、入れ替えます。
❸この操作を繰り返して、右側までたどり着いたら、また左にもどって、同じ操作を繰り返していきます。
選択ソートでは、整列対象の数字の中から最小値/最大値を "選択" する操作を繰り返す
選択ソート(昇順)では、並び替えたい対象の数字の配列の中から、最小値を "選択" する操作を繰り返していきます。
❶上に示している数字の配列のうち、一番小さい数字("1")を選択して、一番左に移動させます。
❷❶で選択した数字("1")以外の数字の中から、一番小さい数字("2")を選択して、2番目("1" の右隣)に移動させます。
❸この操作を繰り返します。
挿入ソートでは、整列済みの配列の適切な場所に数字を "挿入" する操作を繰り返す
挿入ソート(昇順)では、並び替えたい数字の配列を、"並び替え済み" の配列と "まだ並び替えていない" 配列に分けて、"並び替え済み" の配列に "まだ並び替えていない" 配列から数字を "挿入" する操作を繰り返していきます。
❶ "並び替え済み" の数字の配列を、左から1番目の "5" とします。残り9個の数字の配列は "まだ並び替えていない" 配列ということになります。
❷ "まだ並び替えていない" 配列のうち、左から1番目の数字 "6" を "並び替え済み" の数字の配列の中で適切な場所に挿入します。つまり、"5" の右隣に "6" を挿入することになります。
❸この操作を繰り返します。
参考文献
きたみりゅうじ「キタミ式イラストIT塾 応用情報技術者」技術評論社