Fondamenti di Informatica: esercitazione di laboratorio n. 3 Vettori e ricorsione
Pier Luca Montessoro
NOTA: per tutti gli esercizi proposti si richiede di aggiungere funzioni alla libreria vettori vista a lezione e scrivere opportuni programmi main per provarle, facendo anche uso delle funzioni di lettura e stampa dei vettori già scritte.
1. Massimo e minimo in sottovettore
Si scrivano le funzioni
int massimo_in_sottovettore (int v[], int inizio, int fine);
int minimo_in_sottovettore (int v[], int inizio, int fine);
che restituiscono l’indice dell’elemento contenente la prima occorrenza del valore massimo (o minimo) nella porzione di vettore compresa tra gli indici inizio e fine, estremi inclusi.
2. Selection sort
L’algoritmo Selection Sort permette di ordinare un vettore “sistemando” gli elementi uno per volta partendo da quello di indice più basso. È evidente che nel primo elemento andrà messo il valore minimo che si trova nell’intero vettore. Quindi, il primo passo consiste nel cercare la posizione del valore minimo e scambiare tale valore con quello del primo elemento.
A questo punto resterà da ordinare il sottovettore che parte dal secondo elemento e si potrà ripetere il procedimento cercando il minimo del sottovettore che inizia dal terzo elemento e scambiando tale minimo con il valore in seconda posizione.
A questo punto si ripete ancora con il sottovettore restante e così via finché non resta da ordinare un sottovettore di dimensione 1.
In generale, quindi, si trattta di cercare il minimo nel sottovettore che va da i+1 a nmax-1 e scambiare tale valore con l’elemento in i. Poi si ripete incrementando i finché i < nmax – 1.
Si scriva una funzione che ordini un vettore passato come argomento (insieme alla sua dimensione) utilizzando l’algoritmo Selection Sort.
3. Bubblesort
L’algoritmo Bubblesort permette di ordinare un vettore scambiando il contenuto delle celle adiacenti, facendo “risalire” i valori più bassi. Può essere espresso come segue:
do {
per ogni elemento del vettore (fino al penultimo) {
se elemento[i+1] < elemento[i]
scambia elemento[i] ed elemento[i+1]
}
} while (e` stato effettuato almeno uno scambio) Si implementi in linguaggio C l’algoritmo bubblesort.
4. Bubblesort vs. selection sort
Gli algoritmi di ordinamento dei vettori differiscono tra di loro per l’efficienza (numero di operazioni necessarie per concludere il compito). Da questo punto di vista il comportamento degli algoritmi può anche essere molto differente al variare dei dati presenti nel vettore (per esempio nel caso in cui un vettore sia già quasi ordinato, oppure sia in ordine inverso a quello cercato, ecc.).
Si scriva un programma per confrontare l’efficienza di ordinamento dell’algoritmo bubblesort rispetto al selection sort. Per fare questo, si tenga il conto delle operazioni di confronto e delle operazioni di scambio dei valori effettuate su due vettori riempiti con i medesimi valori iniziali.
5. Ricerca in vettore
Si scriva la funzione di ricerca lineare (cioè scandendo il sottovettore elemento per elemento dall’inizio alla fine) int cerca_in_sottovettore (int v[], int inizio, int fine, int valore_cercato);
che restituisce l’indice dell’elemento contenente la prima occorrenza del valore cercato nella porzione di vettore compresa tra gli indici inizio e fine, estremi inclusi. La funzione deve restituire -1 se il vallore cercato non è presente nel vettore.
NOTA: questo algoritmo rappresenta uno dei rari casi in cui un codice codice non strutturato è più “elegante” e leggibile di un codice strutturato. Quando si trova l’elemento, infatti, si può uscire immediatamente dalla funzione mediante un’istruzione return, restituendo l’indice cercato.
6. Selection sort ricorsivo
L’algoritmo di ordinamento selection sort può essere facilmente implementato in modo ricorsivo, in quanto prevede la “sistemazione” del primo elemento del vettore di dimensione n e poi l’applicazione del medesimo procedimento al sottovettore di dimensione n-1. Il procedimento procede finché la dimensione del sottovettore non diventa pari ad 1.
Si provi a scrivere una funzione di ordinamento mediante selection sort in modo ricorsivo.
