DAA-挿入ソート

挿入ソートは、数字を昇順または降順にソートする非常に簡単な方法です。この方法は、増分方法に従います。これは、ゲームのプレイ時にカードがどのようにソートされるかという手法と比較できます。

ソートする必要がある番号は、*キー*と呼ばれます。挿入ソート方法のアルゴリズムは次のとおりです。

Algorithm: Insertion-Sort(A)
for j = 2 to A.length
   key = A[j]
   i = j – 1
   while i > 0 and A[i] > key
      A[i + 1] = A[i]
      i = i -1
   A[i + 1] = key

分析

このアルゴリズムの実行時間は、指定された入力に大きく依存します。

指定された数値がソートされている場合、このアルゴリズムは O（n） 時間で実行されます。指定された数値が逆順の場合、アルゴリズムは O（n ^ 2 ^） 時間で実行されます。

例

Unsorted list:

|2 |13 |5 |18 |14

1 ^ st ^反復：*

キー= a [2] = 13

a [1] = 2 <13

Swap, no swap

|2 |13 |5 |18 |14

2 ^ nd ^反復：*

キー= a [3] = 5

a [2] = 13> 5

Swap 5 and 13

|2 |5 |13 |18 |14

次に、a [1] = 2 <13

Swap, no swap

|2 |5 |13 |18 |14

3 ^ rd ^反復：*

キー= a [4] = 18

a [3] = 13 <18

a [2] = 5 <18

a [1] = 2 <18

Swap, no swap

|2 |5 |13 |18 |14

4 ^ th ^反復：*

キー= a [5] = 14

a [4] = 18> 14

Swap 18 and 14

|2 |5 |13 |14 |18

次に、a [3] = 13 <14

a [2] = 5 <14

a [1] = 2 <14

So, no swap

|2 |5 |13 |14 |18

最後に、

the sorted list is

|2 |5 |13 |14 |18

Design-and-analysis-of-algorithms-insertion-sort

DAA-挿入ソート

分析

例