挿入ソート | ソートアルゴリズム | アルゴリズムをはじめから

挿入ソートアルゴリズムの解説

挿入ソートとは？

挿入ソートは、配列内の要素を1つずつ確認し、適切な位置に挿入することでソートを行うアルゴリズムです。最初の要素は既にソート済みと見なし、次の要素をその前のソート済みの部分に正しい位置に挿入していきます。この操作を繰り返し、配列全体をソートします。

挿入ソートのステップ

1. 配列の最初の要素を既にソート済みとします。
2. 次の要素を選び、ソート済みの部分における正しい位置に挿入します。
3. これを配列の最後の要素まで繰り返します。

挿入ソートのステップごとの変化

ステップ	リストの状態	挿入された要素
初期状態	[5, 2, 9, 1, 5, 6]	—
1	[2, 5, 9, 1, 5, 6]	2
2	[2, 5, 9, 1, 5, 6]	—
3	[1, 2, 5, 9, 5, 6]	1
4	[1, 2, 5, 5, 9, 6]	5
5	[1, 2, 5, 5, 6, 9]	6

挿入ソートはどのように動いているか

スタート

挿入ソートのJavaScript実装

// 挿入ソートのJavaScript実装
function insertionSort(arr) {
    let len = arr.length;
    for (let i = 1; i < len; i++) {
        let key = arr[i];
        let j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
        console.log(arr); // 途中経過を出力
    }
    return arr;
}

let array = [5, 2, 9, 1, 5, 6];
console.log("ソート前:", array);
console.log("ソート後:", insertionSort(array));

挿入ソートのPython実装

# 挿入ソートのPython実装
def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
        print(arr)  # 途中経過を出力
    return arr

array = [5, 2, 9, 1, 5, 6]
print("ソート前:", array)
print("ソート後:", insertion_sort(array))

まとめ

挿入ソートは、データ量が少ない場合に非常に効率的で、アルゴリズムが比較的簡単に理解できるソート手法です。大規模なデータに対しては他のアルゴリズムに比べて時間がかかるため、適切な状況で使用することが重要です。