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

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

挿入ソートは、一度に 1 つの要素を反復処理し、要素を正しい位置に配置することで要素をソートするために使用される比較ソート アルゴリズムの 1 つです。

各要素は、既にソートされたリストに順番に挿入されます。 ソート済みリストの最初のサイズは XNUMX です。 挿入ソート アルゴリズムにより、k 回目の反復後に最初の k 要素が確実にソートされます。

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

挿入ソートのアルゴリズムには、次の重要な特性があります。

• これは安定した並べ替え手法であるため、等しい要素の相対的な順序は変わりません。
• これは、小さなデータセットには効率的ですが、大きなリストには効果的ではありません。
• 挿入ソートは適応的であるため、部分的にソートされている場合は合計ステップ数が削減されます。 配列 効率化するために入力として提供されます。

挿入方法 Opera仕事？

挿入ソート アルゴリズムでは、挿入操作はソートされていない要素をソートするために使用されます。これは、すでにソートされたリストに新しい要素を挿入するのに役立ちます。

挿入操作の疑似コード:

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

A[N-1] is the element to be inserted in the 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 が既にソートされたリストに挿入されます。

ステップ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] により 2 と 3 の位置が入れ替わるため、A[7] と A[6] を比較します。

ステップ4） A[1] と A[2] を比較すると、A[1] < A[2]、つまり、左に隣接する要素の方が大きくなくなります。 ここで、6 が正しく挿入されたと結論付け、ここでアルゴリズムを停止します。

挿入ソートの仕組み

上で説明した挿入操作は、挿入ソートのバックボーンです。挿入手順はすべての要素に対して実行され、最終的にソートされたリストが得られます。

上の図の例は、データ構造における挿入ソートの動作を示しています。 最初、ソートされたサブリストには 4 つの要素 (つまり 1) だけが存在します。A[3] (つまり 2) を挿入した後、ソートされたサブリストのサイズは XNUMX に増加します。

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

#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コード

#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 挿入ソートのプログラム

#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: 挿入ソートでは、受信時に要素をソートできます。 つまり、要素のリストをすでにソートし、さらにいくつかの要素をリストに追加している場合は、ソート手順全体を再度実行する必要はありません。 代わりに、新しく追加された要素を反復処理するだけで済みます。
• 所定の位置に： 挿入ソート アルゴリズムの空間計算量は一定であり、余分なスペースを必要としません。このアルゴリズムは要素を所定の位置にソートします。
• 安定： 挿入ソートでは、値が等しい場合は要素を交換しません。 たとえば、XNUMX つの要素 x と y が等しく、並べ替えられていないリストでは x が y より前に表示され、並べ替えられたリストでは x が y より前に表示されます。 これにより、挿入ソートが安定します。
• アダプティブ： A 並べ替えアルゴリズム 入力要素または要素のサブセットがすでにソートされている場合、挿入ソートの方が時間がかからない場合、それは適応型ソートです。上で説明したように、挿入ソートの最良の実行時間は O(N) で、最悪の実行時間は O(N^2) です。挿入ソートは、適応型ソート アルゴリズムの XNUMX つです。

挿入ソートの複雑さ

スペースの複雑さ

挿入ソートでは、要素をソートするために余分なスペースは必要なく、スペースの複雑さは一定、つまり O(1) です。

時間の複雑さ

挿入ソートは各要素を同時に反復するため、N 個の要素をソートするには N-1 回のパスが必要です。各パスでは、要素がすでにソートされている場合はスワップが XNUMX 回行われ、要素が降順で配置されている場合はスワップが行われます。

• パス 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(n2): 配列が昇順であるときに降順で並べ替えるのは、最悪のシナリオです。
• 最良のケースの複雑さ: O(n): ベストケースの複雑さは、配列がすでにソートされている場合に発生します。外側のループは n 回実行されますが、内側のループはまったく実行されません。比較は n 回のみです。したがって、この場合、複雑さは線形です。
• 平均的なケースの複雑さ: O(n2): 配列の要素が昇順でも降順でもないごちゃ混ぜな順序で出現する場合に発生します。

製品概要

• 挿入ソートは、比較に基づくソート アルゴリズム メソッドです。
• これは安定した並べ替え手法であるため、等しい要素の相対的な順序は変わりません。
• すべての要素に対して、挿入操作を使用して、ソートされたサブリストに要素を挿入します。
• 挿入ソートは、インプレースソートアルゴリズムです。
• 挿入ソートの最悪かつ平均的な時間計算量は2乗、つまり O(N^XNUMX) です。
• 挿入ソートには補助スペースは必要ありません。