挿入ソート
小さな整列済みのデータに新たな要素を適切に「挿入」していくことで整列済みのデータを拡大させていくというアルゴリズム
以下、手順
1番上のデータを整列済みのデータとする
2番目のデータを整列済みのデータ(まだ要素が1つしかないが)と比較して適切な位置に挿入する
3番目のデータを整列済みのデータ(1番目と2番目のデータ)と比較して適切な位置に挿入する
以上を最後まで繰り返してソート完了
計算量はO(n^2)
バブルソートと挿入ソートと計算量は変わらないが、対象のデータ配列がある程度整理されている場合、挿入回数が減ることが見込める 関連記事