ソートとは
与えられたデータを決められた順で並べ替えること
選択ソート
- データの中から最大のデータを見つける
- そのデータを除外する
- データがなくなるまで1.2を繰り返す
つまり最大のデータを除外していき、除外した順にならべると大きいデータ順に並んでいる
データがｎ個だとすると、データを端から端まで探索する作業をｎ回することになるので
時間計算量はO（ｎ^2）
ソートアルゴリズムとしてはよくない
挿入ソート
- 与えられたデータのうちソートされたデータを左、ソートされていないデータを右に分ける
- 右側の最初のデータを左側のデータと右から左に比較していき挿入する場所を探す
- 右側の最初のデータを左側に挿入する
- 1～3を繰り返す
これの最も早い実行時間は与えられたデータがソート済みのときO(ｎ)
逆に最も遅い実行時間は与えられたデータがソートする順とは反対に並べられているときO（ｎ^2）
平均時間計算量はO(ｎ^2)
平均は選択ソートと同じだが、データが並べられているときやデータが小さいときは有効
ヒープソート
ヒープとは
優先順位を数値として表し、優先順位の高い(数値の大きい)データから出力できるデータ構造
データは2分木で表されている
ヒープソートは
- 入力データを用いてヒープのルールに従って2分木を作成する
- 根から順に取り出し並べる
時間計算量はO(nlogn)（説明は省略）
そこまで高速ではない、実用的ではない
クイックソート
- データが1つならばアルゴリズム終了
- データの中から基準値を決める
- 各データを基準値と比較して、すべてのデータを「基準値より小さいデータ」と「基準値より大きいデータ」の集合に分割する
- 新しくできた2つの集合で1～3を行う
集合が1つのデータで形成されるまで繰り返すことでデータが昇順に並び替えられる
平均時間計算量はデータがｎ個のときO(nlogn)（説明はめんどくさいので省略）
コンピュータで実装する場合は高速
多くの言語で組み込まれているらしいので実装する必要なし