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

[[194165]]

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

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

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

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

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

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

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

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

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

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

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

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

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

まず、ソートする要素のシーケンス全体をいくつかのサブシーケンス（特定の「増分」で区切られた要素で構成）に分割し、それぞれに対して直接挿入ソートを実行します。
次に、増分を 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)

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