ソートの挿入

1.概念

名前の通り、2番目の要素から、整列した要素の間に正しい位置を見つけて挿入するソートです.すなわち,配列中のすべての要素を前から順に並べ替えられた配列部分と比較し,自分の位置を見つけて並べ替えを完了するアルゴリズムである.
次のような配列があるとします.
4 2 3 1
まず、2番目の要素を1番目の要素と比較して、自分の値を検索します.2番目の要素2は4より小さいので、4の前の2の位置は固定されています.
2 4 3 1
次に、3番目の要素を前に並べた1,2番目の要素と比較します.3番目の要素3は2より大きく、4より小さく、その間に位置する.
2 3 4 1
最後に、1は最小の要素で、一番前にあります.
1 2 3 4
次のように並べ替える方法は、**挿入ソート**(挿入ソート)です.
これをcコードとして以下に示す.

2.コード

#include <iostream>
using namespace std;

int main()
{
    int a[100], n, tmp, i, j;
    scanf("%d",&a);

    for(i=0; i<n; i++) scanf("%d",&a[i]);

	// 여기서 두번째 원소부터 차례대로 비교해본다
    for(i=1; i<n; i++){
        tmp = a[i];
     	// 이후 우리가 삽입할 원소 이전부터 차례대로 값을 비교하며 삽입해야할 위치를 찾는다. 
        for(j=i-1; j>=0; j--){
            //삽입하기 위해 위치를 찾으며 배열을 이동시킴
            if(a[j]>tmp) a[j+1]=a[j];
            else break;
        }
        //위치를 찾았을 경우 값을 넣어주기
        a[j+1] = tmp;
    }
    for(i=0; i<n; i++){
        printf("%d ",a[i]);
    }
    return 0;
}

時間の複雑さ

最良の場合、最初からすべての値が整列している場合は、変更を必要とせずに自分の位置をチェックするだけで比較できます.
従って、最適な場合の時間的複雑度はO(n)であるが、最悪の場合、すなわちアレイが逆順に配列されている場合、すべての移動が必要であるため、この場合の時間的複雑度はO(n^2)である.

メリットとデメリット

長所

安全並べ替え方法

入力データの大部分が整列している場合、非常に効率的である可能性があります.

短所

の多くのデータの移動を含む.

のデータ量が大きく、データ量が大きい場合は、不適切な方法である.