Esercitazione di laboratorio n.3
Ricorsione e vettori
Minimo / massimo in (sotto)vettore
• È necessario memorizzare l’indice del minimo corrente, non il valore
• Restituendo l’indice si conosce il valore (leggendolo nel vettore) e si sa dove tale valore è memorizzato (necessario per spostarlo, come nel caso degli
algoritmi di ordinamento)
Esempio: minimo in vettore
indice_minimo = 0;
indice_corrente = 1;
while (indice_corrente < dim) {
if (v[indice_corrente] < v[indice_minimo]) indice_minimo = indice_corrente;
indice_corrente++;
}
return indice_minimo;
Esempio: minimo in sottovettore
indice_minimo = inizio;
indice_corrente = inizio + 1;
while (indice_corrente <= fine) {
if (v[indice_corrente] < v[indice_minimo]) indice_minimo = indice_corrente;
indice_corrente++;
}
return indice_minimo;
Esempio: collaudo di minimo in sottovettore
int main() {
...
dim = leggi_vettore (...
/* provo la funzione sull'intero vettore */
risultato = minimo_in_sottovettore (v, 0, dim-1);
printf ("minimo: v[%d] = %d\n", risultato, v[risultato]);
...
}
Selection sort
parti dal primo elemento del vettore while (non arrivi all'ultimo elemento) {
cerca il minimo nel sottovettore
che inizia dall'elemento considerato
scambia il minimo trovato
con il primo elemento del sottovettore passa all'elemento successivo
}
