こんにちは😀
以前、データを探索するアルゴリズムをみてみました。
今回は、データを整列させるアルゴリズムをみてみます。
整列とは、主にデータの昇順や降順の並べ替えを指します。
整列の代表的なアルゴリズムには、
①基本交換法
②基本選択法
③基本挿入法
があります。
それぞれみていきましょう。
①基本交換法
隣接するデータの大小を比較、必要に応じて入れ替えることで、全体を整列させるのが基本交換法です。
バブルソートとも呼ばれます。
データを昇順とか降順に並べ替える場合に使用します。
昇順を行う場合、隣り合ったデータを比較して、右の方が小さければ左右入れ替えます。それを右方向に順に行って整理していきます。
一旦右まで比較したら、最初に戻って比較を行います。
これは、全てのデータが昇順になるまで実行されます。
②基本選択法
対象となるデータの中から最小値（または最大値）のデータを取り出して、先頭のデータと交換し、これを繰り返すことで全体を整列する方法を基本選択法と言います。
これは、選択ソートとも呼ばれます。
昇順を行う場合、データからまず最小値を探します。
それを見つけたら、左側（先頭）と入れ替えます。
最小値の位置が先頭に確定したら、残りのデータ内の最小値を探して、先頭から二番目に配置する・・・といった処理を繰り返します。
③基本挿入法
対象となるデータ列を「整理済みのもの」と「未整列のもの」とに分け、未整理の側からデータを１つずつ整列済みの列の適切な位置に挿入し全体を整理する方法を、基本挿入法を言います。
これは、挿入ソートとも呼ばれます。
昇順の場合、先頭を「整理済み」とします。
その他のデータを「未整理」として、１つデータを取得します。
整理済みのデータと比較して、小さければ左側（先頭）に配置します。
これを繰り返して、未整理のデータがなくなれば終了です。
整列アルゴリズムの応用
上記で紹介した基本の整列アルゴリズムの他に応用もあるのでいくつかまとめます。
・シェルソート・・一定の間隔置きに取り出した要素で部分列を作り、それぞれ整列して元に戻す。次に間隔を詰めて要素を取り出し制度整列を行います。取り出す間隔が１になるまで繰り返します。
・クイックソート・・中間的な基準値を１つ決めて、それより小さいグループと大きいグループを作ります。
その後、それぞれのグループで基準値を１つ決めて、グループを作る、を繰り返して整理します。
・ヒープソート・・未整理の部分を「順序木」と言われる木構造に構成します。そこから最大値または最小値を取り出して整列済みの側へと移します。これを繰り返して整理する方法です。
・マージソート・・配列の２分割を繰り返して、それぞれ配列要素が１となるまで細分化します。その要素をマージ（併合）して元の配列に戻すのですが、その際にお互いを比較して並べ替えながらマージしていきます。
今回の一言・・・
ソートも普段は、プログラムが自動でやってくれるので意識しませんが、様々な方法と地道なロジックの組み合わせで整理されているのがわかります。
今回はここまで🤚
では、また次回。
コメント