DAA-挿入ソート

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

ソートする必要のある番号は、次のように知られています。 keys。これが挿入ソート法のアルゴリズムです。

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²) 時間。

例

Unsorted list:

2 13 5 18 14

1^st iteration:

キー= a [2] = 13

a [1] = 2 <13

スワップ、スワップなし

2 13 5 18 14

2^nd iteration:

キー= a [3] = 5

a [2] = 13> 5

5と13を交換します

2 5 13 18 14

次に、a [1] = 2 <13

スワップ、スワップなし

2 5 13 18 14

3^rd iteration:

キー= a [4] = 18

a [3] = 13 <18

a [2] = 5 <18

a [1] = 2 <18

スワップ、スワップなし

2 5 13 18 14

4^th iteration:

キー= a [5] = 14

a [4] = 18> 14

18と14を交換します

2 5 13 14 18

次に、a [3] = 13 <14

a [2] = 5 <14

a [1] = 2 <14

したがって、スワップはありません

2 5 13 14 18

最後に、

the sorted list is

2 5 13 14 18