ソートアルゴリズム

参考

ソートを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

挿入ソート

計算量

O(n²)
ほとんど整列済みの数列に対してはほぼO(n)と高速で動作する

概要

• 前半をソート済み部分、後半を未ソート部分で分ける
• 未ソート部分の先頭を、ソート済み部分の最後尾から比較して配置
• 安定している

詳細

258369
緑部分がソート済みの場合、

• まず、8と3を比較し、8を後ろにずらして、 253869
• 次に、5と3を比較し、5を後ろにずらして、 235869
• 最後に、2と3を比較し、3を挿入位置が確定して、235869
• 235869 となり、次は6をどこに挿入するかを考える

バブルソート

計算量

O(n²)
遅い。一連の処理において、ある条件を満たせば次のループへ、ということがない。

概要

挿入ソートと同様に、前半をソート済み部分、後半を未ソート部分で分ける
ソート済み部分の最後尾から順々に比較し、大小逆転していれば交換する
安定している

詳細

12534
緑部分がソート済みの場合、

• まず、4と3を比較し、12534でそのまま
• 次に、3と5を比較し、12354
• 再度、一番最後尾から比較、12345

選択ソート

計算量

O(n²)
遅い。

概要

例によって、前半をソート済み部分、後半を未ソート部分で分ける
未ソート部分から最小の要素を特定し、それを未ソート部分の先頭と交換する
安定なソートではない

詳細

1387945
緑部分がソート済みの場合、

• まず、最小となる4を探す
• 次に、4と8を交換し、1347985
• 上記の処理を繰り返す