DAA - Insertion Sort

A classificação por inserção é um método muito simples de classificar números em ordem crescente ou decrescente. Este método segue o método incremental. Pode ser comparado com a técnica como as cartas são classificadas no momento do jogo.

Os números, que precisam ser classificados, são conhecidos como keys. Aqui está o algoritmo do método de classificação por inserção.

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

Análise

O tempo de execução desse algoritmo depende muito da entrada fornecida.

Se os números fornecidos forem classificados, este algoritmo é executado em O(n)Tempo. Se os números fornecidos estiverem na ordem inversa, o algoritmo é executado emO(n²) Tempo.

Exemplo

Unsorted list:

2 13 5 18 14

1^st iteration:

Chave = a [2] = 13

a [1] = 2 <13

Troca, sem troca

2 13 5 18 14

2^nd iteration:

Chave = a [3] = 5

a [2] = 13> 5

Troca 5 e 13

2 5 13 18 14

Em seguida, a [1] = 2 <13

Troca, sem troca

2 5 13 18 14

3^rd iteration:

Chave = a [4] = 18

a [3] = 13 <18,

a [2] = 5 <18,

a [1] = 2 <18

Troca, sem troca

2 5 13 18 14

4^th iteration:

Chave = a [5] = 14

a [4] = 18> 14

Troca 18 e 14

2 5 13 14 18

Em seguida, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Então, sem troca

2 5 13 14 18

Finalmente,

the sorted list is

2 5 13 14 18