ソートアルゴリズム

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

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

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

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

A non-comparison sorting algorithm that counts occurrences of each element and uses arithmetic to determine positions. Achieves O(n+k) time complexity where k is the range of input values. Ideal for sorting integers within a known, limited range. Forms the basis for radix sort.

A non-comparison sorting algorithm that processes elements digit by digit from least significant to most significant. Uses counting sort as a subroutine for each digit position. Achieves O(d(n+k)) time where d is the number of digits. Excellent for sorting integers or fixed-length strings.

An optimization of insertion sort that allows exchange of elements that are far apart. Uses a gap sequence that decreases to 1, enabling the algorithm to move elements closer to their final positions faster. Named after Donald Shell who invented it in 1959.

A distribution-based sorting algorithm that distributes elements into a number of buckets. Each bucket is then sorted individually using another sorting algorithm. Works best when input is uniformly distributed over a range. Average time complexity is O(n+k).

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

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

Improvement over bubble sort that eliminates small values near the end of the list (turtles). Uses a shrinking gap sequence starting with array length, improving worst-case complexity. Practical for medium-sized datasets where simple implementation is valued over optimal performance.

Simple sorting algorithm similar to insertion sort, named after the way garden gnomes sort flower pots. Moves backward when elements are out of order, then forward again. While O(n²) like bubble sort, its simplicity makes it useful for teaching sorting concepts and handling small datasets.