挿入ソート

基本

カテゴリ: arrays

概要

挿入ソートは配列を先頭から順に走査し、各要素を既にソートされた部分配列の適切な位置に挿入していくソートアルゴリズムです。カードゲームで手札を並べ替える方法に似ています。

アルゴリズム可視化

挿入ソートは配列を先頭から順に走査し、各要素を既にソートされた部分配列の適切な位置に挿入していくソートアルゴリズムです。配列のサイズを調整して、ステップバイステップで実行過程を観察しましょう。

配列サイズを調整

55020

1 / 0

速度: 1x

パフォーマンス指標

比較回数

理論値: ~95

交換回数

理論値: ~95

実行時間

0ms

O(n²)

配列サイズ

空間複雑性: O(1)

注意: 実際の実行時間はブラウザやデバイスのパフォーマンスによって異なります。理論値は平均的なケースに基づいています。

チャート式ビジュアル学習ポイント

挿入ソートの視覚化では、ソート済み部分（緑色で表示）が左から増えていく様子に注目してください。各要素が適切な位置に挿入されるプロセスを観察し、小さな配列や部分的にソートされた配列での効率性を理解しましょう。

挿入ソートの学習ガイド

配列を先頭から順に走査し、各要素を既にソートされた部分配列の適切な位置に挿入していくソートアルゴリズムです。

利点

実装が簡単
小さな配列に対して効率的
安定ソート（同じ値の要素の相対的な順序が保持される）
インプレースソート（追加のメモリをほとんど使用しない）
部分的にソートされた配列に対して効率的
オンラインアルゴリズム（データが到着するたびに処理できる）

欠点

大きな配列に対して非効率的
平均および最悪の場合の時間計算量が O(n²)

アルゴリズム比較

アルゴリズム	最良時間	平均時間	最悪時間	空間

コードテンプレート

Java

Python

public void insertionSort(int[] arr) {
    int n = arr.length;
    
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // keyより大きい要素を右に移動
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        
        // keyを適切な位置に挿入
        arr[j + 1] = key;
    }
}

Java

ひらめきのサポート

問題文に以下のようなキーワードや特徴がある場合、このパターンの適用を検討してみましょう。

ソート挿入インプレース安定ソートオンラインアルゴリズム

チャート式ひらめきポイント

問題を読んだときに、「ソート済み配列で何かを見つける」「二つの要素の関係を調べる」「効率的に配列を操作する」などの特徴があれば、双指針パターンが適用できる可能性が高いです。特に、O(n²)の計算量を避けたい場合に有効です。

このパターンを使用する問題例

1
整数の配列をソートする: [12, 11, 13, 5, 6] → [5, 6, 11, 12, 13]
2
ほぼソートされたログファイルのエントリを完全にソートする
3
リアルタイムで到着するデータを順序付けする

このパターンを使う問題

このパターンを適用して解くことができる実際の問題です。

中

区間のマージ

重複する可能性のある区間の配列が与えられたとき、すべての重複する区間をマージして、重複のない区間の配列を返してください。各区間 intervals[i] = [starti, endi] は、st...