esempio: ordinamento di una sequenza di interi

Ordinamento di una sequenza di interi

Analisi e specifica:

dati di ingresso: sequenza s di n interi
precondizione: n>0
dati di uscita: sequenza s1 di n interi
postcondizione: s1 è una permutazione di s dove $\forall i \in [0, n-2], s1_i \leq s1_{i+1}$

identificatore	tipo	descrizione
s	sequenza	sequenza di interi in input
s1	sequenza	sequenza di interi di output
n	intero	numero di elementi nella sequenza
i	intero	indice per individuare gli elementi nella sequenza

Progettazione:

input sequenza s in un array a di dimensione n
ordina array a di dimensione n (per motivi di efficienza decidiamo di utilizzare un unico array di input e output)
output sequenza s1 contenuta in array a di dimensione n

Raffinamento dei passi 1, 2, 3 con delle nuove funioni: input_array(a, n), ordina_array(a, n), output_array(a, n)

Specifica funzione ordina_array:

Dati di ingresso: array a di interi di dimensione n
Precondizione: n>0
Dati di uscita: array a di interi di dimensione n
Postcondizione: l’array a in output contiene una permutazione degli elementi dell’array a in input e $\forall i \in [0, n-2], a[i] \leq a[i+1]$

identificatore	tipo	descrizione
a	array	array di interi
n	intero	dimensione dell’array
i	intero	indice per individuare gli elementi dell’array

Strategia di ordinamento: Selection Sort

Effettua una visita totale (tutti gli elementi in sequenza) delle posizioni dell’array; per ogni posizione visitata individua l’elemento che dovrebbe occupare quella posizione nell’array ordinato e scambia l’elemento trovato con quello che occupa attualmente la posizione