ChatGPTに教えて貰いました。備忘録として。
代表的なソートアルゴリズム
- バブルソート（Bubble Sort）:
隣接する要素を比較して順序が逆なら交換することを繰り返す。
比較回数がO(n^2)、入れ替え回数がO(n^2)となるため、効率は良くない。 - 選択ソート（Selection Sort）:
未ソート部分から最小（または最大）の要素を選び、先頭の要素と交換することを繰り返す。
比較回数がO(n^2)、入れ替え回数がO(n)となるため、効率はあまり良くない。 - 挿入ソート（Insertion Sort）:
ソート済みの部分に要素を適切な位置に挿入することを繰り返す。
ほぼ整列している場合に効率的で、比較回数がO(n^2)、入れ替え回数がO(n)となる。 - クイックソート（Quick Sort）:
ピボット要素を選び、ピボットより小さい要素と大きい要素に分割し、それぞれ再帰的にソートする。
平均的な場合において、比較回数がO(n log n)と非常に効率的。 - マージソート（Merge Sort）:
分割統治法を用いてリストを分割し、それらをマージしながらソートする。
比較回数がO(n log n)と非常に効率的で、安定している。 - ヒープソート（Heap Sort）:
ヒープ構造を使ってソートする。
比較回数がO(n log n)と効率的で、一定の追加メモリが必要。 - シェルソート（Shell Sort）:
間隔を設定して部分的にソートを行い、徐々に間隔を縮めていく方法。
比較回数がO(n log n)からO(n^2)となり、データのパターンによって効率が変わる。
これらのソートアルゴリズムはそれぞれ特徴と効率性が異なるため、ソート対象のデータの特性によって適切なアルゴリズムを選択することが重要です。