データ構造とアルゴリズムソート - 理解できないなら、私に相談してください

[[194165]]

以下では、主にデータ構造の教科書で紹介されている「10 種類のソートアルゴリズム」について説明します。試験が近づいてきたので、ソートアルゴリズムを復習します。言葉よりも写真のほうが雄弁です。理解できないなら、私を殺してください。

ヒープ ソート、クイック ソート、シェル ソート、直接選択ソートは安定したソート アルゴリズムではありませんが、基数ソート、バブル ソート、直接挿入ソート、バイナリ挿入ソート、リンク リスト挿入ソート、マージ ソートは安定したソート アルゴリズムです。

直接挿入ソート T(n) = O(n^2)

直接挿入ソートの基本的な考え方は、すべてのレコードが挿入されるまで、ソートするレコードをそのキーワードのサイズに応じて、以前にソートされたサブシーケンスの適切な位置に毎回挿入することです。

配列をa[0…n-1]とします。

1. 最初は、a[0]はそれ自体で順序付けられた領域を形成し、順序付けられていない領域はa[1..n-1]です。 i=1とします。
2. a[i]を現在の順序付けられた範囲a[0…i-1]にマージして、順序付けられた間隔a[0…i]を形成します。
3. i++ となり、i==n-1 になるまで 2 番目の手順を繰り返します。並べ替えが完了しました。

バイナリ挿入ソート T(n) = O(n^2)

バイナリ挿入ソートは、直接挿入ソートの単純な改良版です。バイナリ挿入ソートでは、i 番目の要素を挿入する必要がある場合、各要素を 1 つずつ比較するのではなく、次の処理を行います。

1. インデックス 0～i-1 の中間点を計算します。つまり、インデックス i の要素とインデックス (0+i-1)/2 の要素を比較します。インデックス i の要素の値が大きい場合は、(0+i-1)/2～i-1 の半分の範囲で直接検索します。それ以外の場合は、0～(0+i-1)/2 の半分の範囲で検索します。これを半値と呼びます。
2. 半分の範囲で検索する場合は、方法1に従って半分の検索を続けて、検索範囲を1/2、1/4、1/8...に絞り込み、挿入位置を素早く決定できるようにします。

リンクリスト挿入ソート T(n) = O(n^2)

リンク リスト挿入ソートの基本的な考え方は、最初の n-1 個のノードが順番に並んでいると仮定し、最初のノードを取り、適切な位置に到達するまでリンク リストに沿って検索および比較し、「このノード」と「挿入するノード」のポインターを変更することです。

1. リンク リストをヘッド ノードに沿ってトラバースし、このノード、挿入するノード、および後続ノードのサイズ関係を、このノード < 挿入するノード < 後続ノードになるまで比較します。
2. 「このノード」が「挿入されるノード」を指し、「挿入されるノード」が「後続ノード」を指すようにします。

シェルソートT(n) = O(n^1.5)

シェルソートの本質はグループ挿入ソートであり、縮小増分ソートとも呼ばれます。この方法の基本的な考え方は次のとおりです。

1. まず、ソートする要素のシーケンス全体をいくつかのサブシーケンス（特定の「増分」で区切られた要素で構成）に分割し、それぞれに対して直接挿入ソートを実行します。
2. 次に、増分を 1 つずつ減らして、再度ソートします。シーケンス全体の要素が基本的に順序付けられたら (増分が 1 と十分に小さい場合)、すべての要素に対して直接挿入ソートを実行します。

バブルソートT(n) = O(n^2)

バブルソートの基本的な考え方は、隣接する要素をペアで比較し、順序が逆の場合はそれらを交換することです。このようにして、最小または最大の要素が各移動で一番上に「浮かび」、最終的に完全な順序が達成されます。

クイックソート範囲T(n) = O(n*lg n) ~ O(n^2) | 平均 T(n) = O(n*lg n)

クイックソートは分割統治（再帰）方式を使用します。その基本的な考え方は次のとおりです。

まず、シーケンスから基数として数字を取ります。

分割プロセスでは、この数値より大きいすべての数値は右側に配置され、この数値以下のすべての数値は左側に配置されます。

各間隔に数字が 1 つだけになるまで、左と右の間隔に対して 2 番目の手順を繰り返します。

直接選択ソートT(n) = O(n^2)

ストレート セレクト ソートもシンプルなソート方法です。基本的な考え方は次のとおりです。

1. R[0]～R[n-1]から最小値を選択し、R[0]と交換する
2. R{1}～R[n-1]から最小値を選択し、R[1]と交換する
3. i回目はR[i-1]～R[n-1]の中から最小値を選択し、R[i-1]と交換する。

ヒープ選択ソートT(n) = O(n*log2n)

ヒープソートとは、ヒープツリー（ヒープ）のデータ構造を使用して設計されたソートアルゴリズムを指します。選択ソートの一種です。杭は大根杭と小根杭に分けられます。次の図は小根杭です。

「図のように同じ手順で行ってください」

マージソートT(n) = O(n*log2n)

マージソートは、分割統治の考え方を採用したマージ操作に基づく効果的なソートアルゴリズムです。双方向のマージを以下に示します。

基数ソート

基数ソートは「分散ソート」の一種であり、「バケットソート」に多少似ています。

1. 10個のバケツを割り当て、バケツに0から9までの番号を付け、1桁の数字をバケツ番号としてバケツを並べ、バケツの中の数字を順番に取り出す。
2. もう一度バケットを入力しますが、今回は10桁の数字を基準にして、対応するバケットを入力します。同じバケットが順番に入力されます
3. もう一度取り出して仕分け完了