概要
アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。
実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。
挿入ソート
- データ列の先頭から順番にソートしていく
- ソート済みと未ソートでそれぞれ部分列に分けられる
- 1回目：0番目をソート済みとするので何もしない
- 2回目：0番目と1番目を比較して順序が逆なら入れ変える
- 3回目：0番目から1番目までのデータ列と比較、順序入れ替え
- 4回目：0番目から2番目までのデータ列と比較、順序入れ替え
- 以下、未ソート部分がなくなるまで繰り返す
計算時間
- O(n²)
実装
- 要素を順番に処理していって、スワップするだけなので単純。