テクノロジ
挿入ソートとは
読み方：そうにゅうソート
ひとことで言うと：整列済み部分の適切な位置へ次の要素を挿入していく整列法。
意味をわかりやすく解説
挿入ソートは、先頭側を整列済み部分として保ち、次の要素を正しい位置へ挿入して整列済み範囲を広げる方法です。
平均・最悪計算量はO(n²)ですが、ほぼ整列済みのデータでは要素移動が少なく高速に動作します。一般に安定ソートとして実装できます。
具体例
[1,4,5]まで整列済みで次の要素が3なら、4と5を右へずらし、[1,3,4,5]にします。
似た用語との違い
覚え方
トランプを手札の正しい位置へ1枚ずつ差し込むイメージ。
基本情報技術者試験の試験ポイント
ほぼ整列済みで効率がよいこと、途中で要素を右へずらす処理を擬似言語で追えるようにします。
CHECK QUESTION
ほぼ昇順に並んだデータに対して、選択ソートより挿入ソートが有利になりやすい理由は何ですか。
答えを見る
挿入位置が近く、要素の比較・移動が少なく済むためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。