定義
挿入ソートは、カードゲームで手札を整理するように、各要素をすでに整列された部分の正しい位置に1つずつ差し込む整列方法です。
主な特性
- ✓前から整列済み部分を徐々に拡大 - 左側は常に整列済み
- ✓ほぼ整列されたデータで非常に速い - 最良の場合O(n)
- ✓安定ソート - 同じ値の順序が保持される
- ✓小さいデータに効率的 - 単純で追加メモリ不要
活用事例
こんな場面で使われます:
🃏
カードゲーム整列
ゲーム中に1枚ずつ受け取ったカードを手札で順番に整理
📊
リアルタイムデータ整列
データが1つずつ入ってくるたびにすぐに整列済みリストに追加
⚡
ほぼ整列されたデータ
すでにほぼ整列されたデータを素早く完全に整列
主な操作
主な操作:
挿入位置を探す
O(n)新しい要素が入る正しい位置を整列済み部分で探します。
挿入
O(1)要素を整列済み部分の正しい位置に入れます。
計算量
時間計算量
最良
O(n)
平均
O(n²)
最悪
O(n²)
空間計算量
O(1)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始