Insertion Sort

Scopo

Ordinamento di un vettore tramite l’algoritmo dell’insertion sort.

Specifiche

void insertion_sort(int n, int A[])

Descrizione

a) Background del problema

L’insertion sort è un algoritmo per l’ordinamento di un array.

E’ un algoritmo “in place” quindi ordina l’array senza fare una copia dell’array stesso,

risparmiando memoria.

I suoi vantaggi sono:

1) E’ molto semplice da implementare

2) E’ molto veloce per ordinare array che sono già ordinati nella loro maggior

parte

b) Breve descrizione dell’algoritmo

L'insertion sort sfrutta due indici: il primo punta all'elemento da ordinare il secondo punta

a quello appena precedente.

Ogni elemento puntato dal secondo indice se è maggiore a quello puntato al primo

indice, viene scambiato col precedente.

P-Like:

procedure ord_inseri(in:N; inout:A)

var n: integer

var a: array(1...n) of character

var next: character

begin for i=2,n do

next := a(i)

j:=i-1

while j>=1 and next <a(j)

a(j+1) := a(j)

j=j-1

endwhile

a(j+1) := next

endfor

end

Riferimenti Bibliografici

A.Murli, G. Laccetti, et al., Laboratorio di Programmazione I, pag 177 Liguori 2003