ソートアルゴリズム

隣接する要素を繰り返し比較し、順序が間違っている場合に交換する最も基本的なソートアルゴリズムです。泡が水面に上がるように、大きな値が徐々に配列の末尾に移動します。小規模なデータセットやソートの基礎を理解するための教育目的に最適です。

最小の要素を見つけて繰り返し前方に移動させます。各反復で残りの要素から最小値を「選択」し、ソート済み部分の後ろに配置します。メモリ使用量は最小限でシンプルに実装できますが、入力に関係なく常にO(n²)の時間がかかります。

ピボット要素を選択し、小さい値を左側、大きい値を右側に配置して配列を分割する非常に効率的なソートアルゴリズムです。平均O(n log n)で、実際に最も広く使用されているソート方法です。ほとんどのプログラミング言語の組み込みソート関数の基盤となっています。

最大ヒープを構築し、ルート要素を繰り返し抽出してソートする二分ヒープデータ構造を使用します。すべての場合でO(n log n)の時間計算量を保証し、追加メモリを必要としません。優先度付きキューの実装の基礎にもなっています。

各要素の出現回数をカウントし、算術演算を使用して位置を決定する非比較ソートアルゴリズムです。入力値の範囲をkとして、O(n+k)の時間計算量を達成します。既知の限られた範囲内の整数のソートに理想的です。基数ソートの基礎を形成します。

最下位桁から最上位桁まで桁ごとに要素を処理する非比較ソートアルゴリズムです。各桁位置にカウンティングソートをサブルーチンとして使用します。桁数をdとしてO(d(n+k))時間を達成します。整数や固定長文字列のソートに優れています。

離れた要素の交換を可能にする挿入ソートの最適化です。1まで減少するギャップシーケンスを使用し、アルゴリズムが要素を最終位置により早く移動できるようにします。1959年にこれを発明したDonald Shellにちなんで名付けられました。

要素をいくつかのバケットに分配する分布ベースのソートアルゴリズムです。各バケットは別のソートアルゴリズムを使用して個別にソートされます。入力が範囲内で均一に分布している場合に最も効果的です。平均時間計算量はO(n+k)です。

配列を半分に分割し、各半分を再帰的にソートしてから結合する分割統治アルゴリズムです。O(n log n)の時間を保証し、安定ですが、追加メモリが必要です。大規模なデータセットや連結リストのソートに特に効果的です。

手札のカードをソートするように、各要素を一度に適切な位置に挿入します。既にソート済みのデータに対してO(n)時間で実行されるため、小規模な配列やほぼソート済みのデータセットに非常に効率的です。シンプルながら適応的なアルゴリズムです。

リストの末尾近くの小さな値（亀）を排除するバブルソートの改良版です。配列長から始まる縮小ギャップシーケンスを使用し、最悪ケースの複雑さを改善します。シンプルな実装が最適なパフォーマンスよりも重視される中規模データセットに実用的です。

挿入ソートに似たシンプルなソートアルゴリズムで、庭のノームが植木鉢をソートする方法にちなんで名付けられました。要素が順序通りでない場合は後退し、再び前進します。バブルソートと同様にO(n²)ですが、そのシンプルさがソートの概念を教えたり小規模データセットを扱うのに役立ちます。