次の数値を考慮してください。
50 60 30 10 80 70 20 40
このリストを昇順で並べ替えると、次のようになります。
10 20 30 40 50 60 70 80
降順に並べ替えると、次のようになります。
80 70 60 50 40 30 20 10
挿入ソートは、リストを昇順または降順でソートするために使用されるソート・アルゴリズムです。この記事では、昇順の並べ替えのみを扱います。降順での並べ替えは、このドキュメントで説明されているのと同じロジックに従います。この記事の目的は、挿入ソートについて説明することです。次の例では、C でプログラミングを行います。ここでは、1 つの配列を使用して挿入ソートについて説明します。
挿入ソートのアルゴリズム
ソートされていないリストが表示されます。目的は、同じリストを使用して昇順でリストをソートすることです。同じ配列を使用してソートされていない配列をソートすることは、インプレースソートと呼ばれます。ここでは、ゼロ ベースのインデックスが使用されます。手順は次のとおりです。
-
- リストは最初からスキャンされます。
- スキャンが進行している間、その前任者よりも少ない番号はその前任者と交換されます。
- このスワップは、スワップできなくなるまで、リストに沿って続行されます。
- スキャンが終了すると、ソートが完了します。
挿入ソート図
時間の複雑さを扱う場合、通常考慮されるのは最悪のケースです。前のリストの最悪の配置は次のとおりです。
80 70 60 50 40 30 20 10
0 から 7 までのインデックスを持つ 8 つの要素があります。
インデックス 0 で、スキャンは 80 に進みます。これが 1 つの動きです。この1つの動きが操作です。ここまでで合計 1 回の操作があります (1 回の移動、比較なし、スワップなし)。結果は次のとおりです。
| | 80 70 60 50 40 30 20 10
インデックス 1 では、70 への移動があります。70 は 80 と比較されます。70 と 80 が交換されます。 1回の動作が1回の動作です。 1 回の比較も 1 回の操作です。 1 回のスワップも 1 回の操作です。このセクションでは、3 つの操作について説明します。これまでに合計 4 つの操作が行われています (1 + 3 = 4)。結果は次のとおりです。
70 | 80 60 50 40 30 20 10
インデックス 2 では、60 への移動があります。60 が 80 と比較され、次に 60 と 80 が交換されます。 60 と 70 を比較し、60 と 70 を入れ替えます。 1回の動作が1回の動作です。 2 つの比較は 2 つの操作です。 2 つのスワップは 2 つの操作です。このセクションでは、5 つの操作について説明します。これまでに合計 9 回の操作が行われています (4 + 5 = 9)。結果は次のとおりです。
60 70 | 80 50 40 30 20 10
インデックス 3 では、50 への移動があります。50 は 80 と比較され、次に 50 と 80 が交換されます。 50 が 70 と比較され、50 と 70 が交換されます。 50 が 60 と比較され、50 と 60 が交換されます。 1回の動作が1回の動作です。 3 つの比較は 3 つの操作です。 3 つのスワップは 3 つの操作です。このセクションでは、7 つの操作について説明します。これまでに合計 16 回の操作が行われています (9 + 7 = 16)。結果は次のとおりです。
50 60 70 | 80 40 30 20 10
インデックス 4 では、40 への移動があります。40 は 80 と比較され、次に 40 と 80 が交換されます。 40 が 70 と比較され、40 と 70 が交換されます。 40 が 60 と比較され、40 と 60 が交換されます。 40 が 50 と比較され、40 と 50 が交換されます。 1回の動作が1回の動作です。 4 つの比較は 4 つの操作です。 4 つのスワップは 4 つの操作です。このセクションでは、9 つの操作を提供します。これまでに合計 25 回の操作が行われています (16 + 9 = 25)。結果は次のとおりです。
40 50 60 70 80 | 30 20 10
インデックス 5 では、30 への移動があります。30 は 80 と比較され、次に 30 と 80 が交換されます。 30 が 70 と比較され、30 と 70 が交換されます。 30 と 60 を比較し、30 と 60 を入れ替えます。 30 が 50 と比較され、30 と 50 が交換されます。 30 と 40 を比較し、30 と 40 を入れ替えます。 1回の動作が1回の動作です。 5 つの比較は 5 つの操作です。 5 つのスワップは 5 つの操作です。このセクションでは、11 の操作について説明します。これまでに合計 36 回の操作が行われました (25 + 11 = 36)。結果は次のとおりです。
30 40 50 60 70 80 | 20 10
インデックス 6 では、20 への移動があります。20 は 80 と比較され、次に 20 と 80 が交換されます。 20 が 70 と比較され、20 と 70 が交換されます。 20 と 60 を比較し、20 と 60 を入れ替えます。 20 が 50 と比較され、20 と 50 が交換されます。 20 と 40 を比較し、20 と 40 を入れ替えます。 20 と 30 を比較し、20 と 30 を入れ替えます。 1回の動作が1回の動作です。 6 回の比較は 6 回の操作です。 6 回のスワップは 6 回の操作です。このセクションでは、13 の操作について説明します。これまでに合計 49 回の操作が行われています (36 + 13 = 49)。結果は次のとおりです。
20 30 40 50 60 70 80 | 10
インデックス 7 では、10 への移動があります。10 は 80 と比較され、次に 10 と 80 が交換されます。 10 と 70 を比較し、10 と 70 を入れ替えます。 10 と 60 を比較し、10 と 60 を入れ替えます。 10 と 50 を比較し、10 と 50 を入れ替えます。 10 と 30 を比較し、10 と 40 を入れ替えます。 10 と 30 を比較し、10 と 30 を入れ替えます。 10 と 20 を比較し、10 と 20 を入れ替えます。 1回の動作が1回の動作です。 7 回の比較は 7 回の操作です。 7 つのスワップは 7 つの操作です。このセクションでは、15 の操作について説明します。これまでに合計 64 回の操作が行われています (49 + 15 = 64)。結果は次のとおりです。
10 20 30 40 50 60 70 80 10 |
仕事は終わった！ 64の操作が含まれていました。
64 = 8 × 8 = 8 2
挿入ソートの時間計算量
前に示したように、挿入ソートでソートする要素が n 個ある場合、可能な操作の最大数は n2 になります。挿入ソート時間の複雑さは次のとおりです。
の上 2 )
これは Big-O 表記を使用します。 Big-O 表記は、大文字の O で始まり、その後に括弧が続きます。括弧内は、可能な最大操作数の式です。
C でのコーディング
スキャンの開始時に、最初の要素の位置を変更することはできません。プログラムは基本的に次のとおりです。
#includeボイド挿入並べ替え ( 整数 A [ ] , int N ) {
為に ( 整数 私 = 0 ;私 < N; i++ ) {
int j = i;
その間 ( あ [ j ] < あ [ j- 1 ] && j- 1 > = 0 ) {
内部温度 = A [ j ] ;あ [ j ] = A [ j- 1 ] ;あ [ j- 1 ] = 温度; /// スワップ
j--;
}
}
}
insertSort() 関数定義は、説明されているアルゴリズムを使用します。 while ループの条件に注意してください。このプログラムに適した C main 関数は次のとおりです。
{
整数 n = 8 ;
整数 A [ ] = { 50 、 60 、 30 、 10 、 80 、 70 、 20 、 40 } ;
挿入ソート ( あ、ん ) ;
為に ( 整数 私 = 0 ;私 < n; i++ ) {
printf ( '％私 ' 、あ [ 私 ] ) ;
}
printf ( ' \n ' ) ;
戻る 0 ;
}
結論
挿入ソートの時間計算量は次のように与えられます。
の上 2 )
読者は、最悪の場合の時間計算量、平均的な場合の時間計算量、および最良の場合の時間計算量について聞いたことがあるかもしれません。 Insertion Sort Time Complexity のこれらのバリエーションについては、Web サイトの次の記事で説明します。