C言語による挿入ソートアルゴリズム C++, Java, Python 例

挿入ソートとは何ですか?

挿入ソートは、比較ソートアルゴリズムの一つであり、要素を一つずつ順番に処理し、既に順序付けられた領域内の正しい位置に配置することで要素をソートする。

各要素は、既にソート済みのリストに順次挿入されます。ソート済みのリストの初期サイズは1です。挿入ソートアルゴリズムは、外側のループのk回目の反復後に最初のk個の要素がソートされていることを保証します。

挿入ソートは結果を段階的に構築するため、教えやすく、デバッグも容易であり、より複雑なアルゴリズムではオーバーヘッドが増えるだけで目立ったメリットが得られないような非常に小さな入力に対しては、強力なベースラインとなる。

挿入ソートアルゴリズムの特徴

挿入ソートのアルゴリズムには、実際のワークロードにおける動作を説明する以下の重要な特徴があります。

• これは安定した並べ替え手法であるため、等しい要素の相対的な順序は変わりません。
• 小規模なデータセットには効率的だが、二次関数的な増加が支配的な大規模リストには効果的ではない。
• 挿入ソートは適応型であり、入力が部分的にソートされている場合は総ステップ数を削減します。 配列 入力として提供されるのは、ランダムアクセスによって内部ループ中に一定時間でのシフトが可能になるため、効率性を高めるためです。
• これはインプレースアルゴリズムであるため、入力サイズに比例した補助ストレージを必要としません。

これらの特性を踏まえ、次のセクションでは、アルゴリズムの各パスを支える中核となる挿入操作について説明します。

挿入方法 Opera仕事？

挿入ソートアルゴリズムでは、挿入操作は未ソートの要素をソートするために使用されます。挿入操作は、既にソートされたリストに新しい要素を挿入する際に、ソート済みの領域の既存の順序を維持するのに役立ちます。

挿入操作の擬似コード：

N 個の要素からなるリスト A を考えてみましょう。

// Insert A[N-1] into sorted sublist A[0..N-2]
for i = N-1 to 1:
    if A[i] < A[i-1], then swap A[i] and A[i-1]
    else stop

上記の例では、既にソートされたリストに新しい要素6が挿入されます。 trac新しい要素が正しい位置に向かって左に移動するにつれて、内側のループが実行されます。

ステップ1） A[5]、9 > 6 の左隣の要素と比較して、9 と 6 の位置を交換します。今度は要素 6 が A[4] に移動されます。

ステップ2） ここで、A[4]とA[3]を比較すると、A[3] > A[4]であることがわかります。そこで、再び6と8の位置を入れ替えます。

ステップ3） 次に、A[3]とA[2]を比較します。A[2] > A[3]なので、7と6の位置を入れ替えます。

ステップ4） A[1]とA[2]を比較します。A[1] < A[2]であるため、左隣の要素はもはやA[1]より大きくありません。したがって、6が正しく挿入されたと結論付け、ここで内側のループを終了します。

挿入ソートの仕組み

上述の挿入操作は、挿入ソートの根幹を成すものです。挿入処理はすべての要素に対して実行され、最終的にソートされたリストが得られます。これは、外側のパスごとにソート領域が1つずつ要素ずつ増えていくためです。

上の図は、データ構造における挿入ソートの動作を示しています。最初は、ソートされたサブリストには要素が1つだけ（4）あります。A[1]（3）を挿入すると、ソートされたサブリストのサイズは2に増え、アルゴリズムはすべての要素が配置されるまでこのパターンを続けます。

概念的な流れが整ったので、次のセクションでは具体的な実装を示します。 C++、C、および Python これにより、異なる言語間でループ構造を比較できます。

C++ 挿入ソートのプログラム

その C++ 以下の実装では、2つのネストされたループを使用しています。外側のループは次にソートされていない要素を選択し、内側のループは正しい位置が見つかるまでその要素を左にシフトします。

#include <iostream>
using namespace std;

int main(){
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    cout << "\nUnsorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    int current_element,temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    cout << "\nSorted: ";
    for(int i = 0 ; i < size_unsorted ; i++){
        cout << unsorted[i] << " ";
    }

    return 0;
}

出力：

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

C Code 挿入ソートの場合

同じロジックはC言語にもそのまま適用できます。 printf 呼び出しはストリーム出力を置き換えますが、内側のループ内のスワップパターンは、 C++ バージョン。

#include <stdio.h>
int main() {
    //unsorted list
    int unsorted[] = {9,8,7,6,5,4,3,3,2,1};

    //size of list
    int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]);

    //printing unsorted list
    printf("\nUnsorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    int current_element, temp;

    for(int i = 1; i < size_unsorted; i++){
        current_element = unsorted[i];
        for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){
            //swapping if current element is lesser
            temp = unsorted[j+1];
            unsorted[j+1] = unsorted[j];
            unsorted[j] = temp;
        }
    }

    //printing sorted list
    printf("\nSorted: ");
    for(int i = 0 ; i < size_unsorted ; i++){
        printf("%d ", unsorted[i]);
    }

    return 0;
}

出力：

Output:
Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

Python 挿入ソートのプログラム

Python タプルスワップをサポートping 単一の式で、内側のループは C よりもコンパクトで、 C++ 同じアルゴリズム動作を維持しながら、対応する機能を実現する。

#unsorted list
unsorted = [9,8,7,6,5,4,3,3,2,1]

#size of list
size_unsorted = len(unsorted)

#printing unsorted list
print("\nUnsorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

for i in range(1, size_unsorted):
    current_element = unsorted[i]
    j = i - 1
    while j >= 0 and unsorted[j] > current_element:
        #swapping if current element is lesser
        unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1]
        j -= 1

#printing sorted list
print("\nSorted: ", end="")
for i in range(size_unsorted):
    print(unsorted[i], end=" ")

出力：

Unsorted: 9 8 7 6 5 4 3 3 2 1
Sorted: 1 2 3 3 4 5 6 7 8 9

挿入ソートのプロパティ

挿入ソートが適切なツールであるかどうかを判断するのに役立つ重要な特性を以下に示します。

• Online: 挿入ソートは、要素を受け取ると同時にソートを実行できます。既にソート済みの要素リストにさらに要素を追加した場合、ソート処理全体を再度実行する必要はありません。代わりに、新しく追加された要素のみを反復処理します。
• 所定の位置に： 挿入ソートアルゴリズムの空間計算量は定数であり、追加のメモリを必要としません。このアルゴリズムは要素をその場でソートします。
• 安定： 挿入ソートでは、値が等しい要素は交換しません。例えば、xとyという2つの要素が等しく、ソート前のリストでxがyより前に表示されている場合、ソート後のリストでもxはyより前に表示されます。このため、挿入ソートは安定ソートとなります。
• アダプティブ： A 並べ替えアルゴリズム 入力要素または要素のサブセットが既にソートされている場合に処理時間が短縮される場合、それは適応的であると言えます。前述のように、挿入ソートの最良の実行時間はO(N)であり、最悪の実行時間はO(N^2)です。挿入ソートは適応型ソートアルゴリズムの1つです。

挿入ソートの複雑さ

以下の複雑性に関する議論では、メモリ使用量と実行時間の両方を取り上げ、挿入ソートを他のアルゴリズムと比較できるようにしています。 Bubble 並べ替え (NAIST) と クイックソート.

スペースの複雑さ

挿入ソートは、要素をソートするために追加のメモリ領域を必要としません。入力サイズに関係なく、使用する一時変数がごく少数であるため、空間計算量は定数、つまりO(1)となります。

時間の複雑さ

挿入ソートは一度に1つの要素を処理するため、N個の要素をソートするにはN-1回のパスが必要です。各パスにおいて、要素が既にソートされている場合はスワップは0回で済みますが、要素が降順に並んでいる場合は多くのスワップが必要になる場合があります。

• パス 1 の場合、必要な最小スワップは 1、最大スワップは XNUMX です。
• パス 2 の場合、必要な最小スワップは 2、最大スワップは XNUMX です。
• パス N の場合、必要な最小スワップは XNUMX で、必要な最大スワップは N です。
• 最小スワップはゼロなので、N 回のパスを反復する場合の最適な時間計算量は O(N) です。
• 交換回数の最大値は (1+2+3+4+…+N) つまり N(N+1)/2 なので、最悪の時間計算量は O(N^2) です。

挿入ソートの重要な時間計算量は以下のとおりです。

• 最悪の場合の複雑さ: O(n^2): 昇順でソートする必要がある配列を降順でソートするのは最悪のシナリオです。
• 最良のケースの複雑さ: O(n): 最良のケースは、配列が既にソートされている場合です。外側のループはn回実行されますが、内側のループは全く実行されません。比較回数はn回だけなので、計算量は線形です。
• 平均的なケースの複雑さ: O(n^2): これは、配列の要素が昇順でも降順でもない、ランダムな順序で出現する場合に発生します。

よくあるご質問