バブルソート
基本的なソートのアルゴリズムを説明しよう。 数字を書いたカードを配列の要素に見立てて、 昇順 (小さい順) バブルソート、選択ソート、 ゾート、マージソート、クイックソートを、 手作業で行う手順を示す。 手作りのカードを用意して、実際にやってみよう。
最初は、バブルソートである。 バブルソートのアルゴリズムは、「配列の末尾から先頭に向かって、隣同士の要素を比較し、 小さい方が前になるように交換する」 である。 小さい要素が泡のように浮かび上がってくるので、バブル （bubble =泡）ソートと呼ぶ。 下図は、4枚のカードを手作業でバブルソートする手順である。
選択ソート
次は、選択ソートである。選択ソートのアルゴリズムは、「配列の先頭から末尾に向かって、要素の値をチェックして、最小値を選択し、それを先頭の要素と交換する」 である。 下図は、4枚のカードを手作業で選択ソートする手順である。
挿入ソート
次は、挿入ソートである。挿入ソートのアルゴリズムは、「配列の2番目から末尾に向かって、要素を1つずつ取り出し、それより前の部分の適切な位置に挿入する」である。下図は、4枚のカードを手作業で挿入ソートする手順である。1番目のカード [4] を挿入済みとして、スタートする。
マージソート
次は、マージソートです。 マージ (merge) とは 「結合」という意味である。 マージソートのアルゴリズムは、 「配列を要素数が1個になるまで分割し、分割した配列から、要素を小さい順に取り出して結合する」である。 下図は、4枚のカードを手作業でマージソートする手順である。
クイックソート
最後は、クイックソートである。 クイック (quick)とは「速い」という意味である。
クイックソートのアルゴリズムは、「配列の中から基準値を1つ選び残りの要素を、基準値との大小でグループ分けする」 である。
下図は、7枚のカードを手作業でクイックソートする手順である。
クイックソートの手順は、 データ数が少ないとわかりにくいので、4枚ではなく7枚のカードを使っている。 この例では、グループに分けたカードがちょうど半分ずつになっているが、実際には、 どちらかのグループに偏ることの方が多いだろう。
グループ分けは、置かれたカードの枚数が1枚になるまで繰り返す。
基準のカードおよびグループ分けしたときに1枚になったカードは、位置が確定する。
（参考）情報処理教科書 出るとこだけ！基本情報技術者［科目A］［科目B］2025年
コメント