DAA - Ordinamento di inserzione

L'ordinamento per inserzione è un metodo molto semplice per ordinare i numeri in ordine crescente o decrescente. Questo metodo segue il metodo incrementale. Può essere paragonato alla tecnica di come vengono ordinate le carte al momento di una partita.

I numeri, che devono essere ordinati, sono noti come keys. Ecco l'algoritmo del metodo di ordinamento per inserzione.

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

Analisi

Il tempo di esecuzione di questo algoritmo dipende molto dall'input fornito.

Se i numeri dati vengono ordinati, questo algoritmo viene eseguito O(n)tempo. Se i numeri dati sono in ordine inverso, l'algoritmo viene eseguitoO(n²) tempo.

Esempio

Unsorted list:

2 13 5 18 14

1^st iteration:

Chiave = a [2] = 13

a [1] = 2 <13

Swap, no swap

2 13 5 18 14

2^nd iteration:

Chiave = a [3] = 5

a [2] = 13> 5

Scambia 5 e 13

2 5 13 18 14

Successivamente, a [1] = 2 <13

Swap, no swap

2 5 13 18 14

3^rd iteration:

Chiave = 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 iteration:

Chiave = a [5] = 14

a [4] = 18> 14

Scambia 18 e 14

2 5 13 14 18

Successivamente, a [3] = 13 <14,

a [2] = 5 <14,

a [1] = 2 <14

Quindi, nessuno scambio

2 5 13 14 18

Finalmente,

the sorted list is

2 5 13 14 18