ソートアルゴリズムを簡単に学ぶ: よく使われるソートアルゴリズムを視覚的に体験

1. クイックソート

導入：

クイックソートは、Tony Hall によって開発されたソートアルゴリズムです。平均すると、n 個の項目をソートするには O(n log n) 回の比較が必要です。最悪の場合、O(n2) 回の比較が必要になりますが、これは一般的ではありません。実際、クイックソートは、その内部ループがほとんどのアーキテクチャで効率的に実装でき、ほとんどの実世界のデータでは設計の選択によって必要な時間を 2 乗項で短縮できる可能性が決まる可能性があるため、他の O(n log n) アルゴリズムよりも大幅に高速になることがよくあります。

ステップ：

◆ シーケンスから要素を選択することを「ピボット」と呼びます。

◆ シーケンスを並べ替えて、基本値より小さいすべての要素をベースの前に置き、基本値より大きいすべての要素をベースの後ろに配置します (同じ数字がどちらの側にある場合もあります)。このパーティションを削除すると、ベンチマークはランキングの中間になります。これをパーティション操作と呼びます。

◆ 基本値より小さい要素の部分列と基本値より大きい要素の部分列を再帰的にソートします。

ソート効果:

2. マージソート

導入：

マージソート（Merge sort、台湾ではmerge sortと訳される）は、マージ操作に基づく効果的なソートアルゴリズムです。このアルゴリズムは分割統治の典型的な応用である。

ステップ：

◆ 2 つのソートされたシーケンスの合計サイズを持つスペースを申請します。このスペースは、マージされたシーケンスを格納するために使用されます。

◆ 2つのポインタを設定し、その初期位置は2つのソートされたシーケンスの開始位置となる

◆ 2つのポインタが指す要素を比較し、比較的小さい要素を選択してマージスペースに配置し、ポインタを次の位置に移動します。

◆ ポインタがシーケンスの最後に到達するまでステップ3を繰り返す

◆ 他のシーケンスの残りの要素をすべて、結合されたシーケンスの末尾に直接コピーします。

ソート効果:

3. ヒープソート

導入：

ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。ヒープは、完全なバイナリツリーを近似し、ヒーププロパティを満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さい (または大きい) です。

ステップ：

（かなり複雑なので、オンラインで調べてください）

ソート効果:

4. 選択ソート

導入：

選択ソートはシンプルで直感的なソートアルゴリズムです。仕組みは以下のとおりです。まず、ソートされていないシーケンス内の最小の要素を見つけて、ソートされたシーケンスの先頭に格納します。次に、残りのソートされていない要素から最小の要素を探し続け、ソートされたシーケンスの最後に配置します。すべての要素がソートされるまでこれを繰り返します。

ソート効果:

5. バブルソート

導入：

バブルソート（Bubble Sort、台湾語ではバブルソートまたはバブルソートと訳される）は、単純なソートアルゴリズムです。ソートする配列を繰り返し処理し、一度に 2 つの要素を比較して、順序が間違っている場合はそれらを交換します。シーケンスを訪問する作業は、交換が不要になるまで、つまりシーケンスがソートされるまで繰り返されます。このアルゴリズムの名前は、小さな要素が交換を通じてゆっくりとシーケンスの先頭に「浮かんで」いくという事実に由来しています。

ステップ：

◆ 隣接する要素を比較します。最初の値が 2 番目の値より大きい場合は、それらを交換します。

◆ 隣接する要素の各ペアに対して、先頭の最初のペアから最後のペアまで同じことを行います。この時点で、最大の要素が最大の数値になるはずです。

◆ 最後の要素を除くすべての要素に対して上記の手順を繰り返します。

◆ 比較する必要のある数字のペアがなくなるまで、要素の数を減らしながら上記の手順を繰り返します。

ソート効果:

6. 挿入ソート

導入：

挿入ソートのアルゴリズムの説明は、シンプルで直感的なソートアルゴリズムです。これは、順序付けられたシーケンスを構築することによって機能します。ソートされていないデータの場合は、ソートされたシーケンス内で後ろから前へスキャンし、対応する位置を見つけて挿入します。挿入ソートは通常、インプレースソート（つまり、O(1)の追加スペースのみを必要とするソート）によって実装されます。したがって、後ろから前へスキャンするプロセスでは、挿入する最初の要素のためのスペースを確保するために、ソートされた要素を繰り返し後方にシフトする必要があります。

ステップ：

◆ 最初の要素から始めて、要素はソートされているとみなすことができます

◆ 次の要素を取り出し、ソートされた要素の順序で後ろから前へスキャンする

◆ 要素（すでにソートされている）が新しい要素よりも大きい場合は、要素を次の位置に移動する

◆ ソートされた要素が新しい要素より小さいか等しい位置が見つかるまで、手順3を繰り返します。

◆ この位置に新しい要素を挿入します

◆ 手順2を繰り返す

ソート効果:

（なし）

7. シェルソート

導入：

ヒルソートは、降順増分ソートアルゴリズムとも呼ばれ、挿入ソートの高速で安定した改良版です。