appunti di fondamenti di informatica e programmazione I

Appunti di Raffaele Ventriglia

Algoritmo di ordinamento per inserimento

L'algoritmo di ordinamento per inserimento è un algoritmo che ha come scopo quello di ordinare un array in ordine crescente, che può avere dati di tipo intero, caratteri o stringhe di caratteri. Ha come dati di input l'array e il suo size e come output lo stesso array ma ordinato; questa tecnica è chiamata anche "in place" in quanto non fa uso di ulteriori strutture dati per poter ordinare l'array.

Utilizza un approccio incrementale al problema dell'ordinamento in quanto ad ogni passo l'algoritmo risolve un'istanza del problema, ovvero trovare la posizione giusta per l'elemento che deve essere ordinato. Quindi al passo i-esimo possiamo dire che la porzione che va da 0 ad i-1 è già ordinata, ma è un ordinamento momentaneo in quanto per ogni passo potrebbe essere trovato un elemento che deve essere posizionato all'interno della porzione in modo tale da trovarsi con gli elementi minori uguali a sinistra e gli elementi maggiori uguali a destra.

L'implementazione in C consiste nell'utilizzo di un for che permette di iterare l'array e un ciclo while innestato che permette il confronto tra l'elemento alla posizione i e l'elemento subito alla sua sinistra, in modo tale da shiftarlo se ce ne sia bisogno per inserirlo nella posizione corretta. La complessità di spazio di questo algoritmo, poiché lavora in place, è n; mentre per la complessità di tempo bisogna prendere in considerazione le operazioni dominanti, che sono il confronto e lo shift tra gli elementi: sia per le operazioni di confronto che per le operazioni di scambio ci viene in aiuto la formula di Gauss, poiché bisogna addizionare i primi n numeri naturali.

Algoritmo di ordinamento per selezione di minimo

L'algoritmo di ordinamento per selezione di minimo permette di ordinare un array in ordine crescente, che può contenere dati di tipo intero, carattere o stringhe di caratteri. Ha come dati di input un array, il suo size e come unico dato di output lo stesso array ordinato; questa tecnica è chiamata anche "in place" in quanto permette di ordinare un array senza l'utilizzo di ulteriori strutture dati.

Questo algoritmo fa un numero di iterazioni che è uguale a size - 1, e ad ogni passo risolve il sotto problema di trovare l'elemento minimo e il suo indice all'interno della porzione data; una volta trovato l'elemento, viene posto al primo posto della porzione dell'array considerato; dopo di che verrà decrementata la porzione e ne verrà considerata una nuova in cui dovrà essere trovato di nuovo l'elemento minimo e il suo indice per poterlo inserire nella prima posizione, che però questa volta è la posizione 2 in quanto è stato già trovato il primo elemento.

Bisogna considerare che l'algoritmo ordina fino a size - 1 in quanto l'ultimo elemento di logica sarà già nella posizione corretta essendo l'unico elemento e quindi il più piccolo tra "gli elementi". In C quest'algoritmo viene implementato attraverso un ciclo for che itera tutti gli elementi dell'array, ma ad ogni iterazione considererà una porzione sempre minore di dati: all'interno di questo for avremo una prima chiamata alla function min_val_ind che permette di trovare l'elemento minore e il suo indice, dopo di che abbiamo una chiamata alla function swap che scambierà l'elemento minore con l'elemento che si trova alla prima posizione della porzione considerata.

La complessità di spazio, poiché lavora in place, è n; per la complessità di tempo invece bisogna prendere in considerazione le operazioni di confronto e di scambio: le operazioni di confronto vengono fatte all'interno della function min_val_ind, ed è costante in quanto viene chiamata n – 1 volte, ma il size della porzione su cui agisce non è costante perché diminuisce di 1 ad ogni iterazione, quindi bisogna fare la somma dei primi n numeri naturali (formula di Gauss); per quanto riguarda invece le operazioni di scambio vengono effettuate una volta per ogni iterazione del ciclo for, quindi si tratta di una complessità assoluta che è uguale a size - 1.

Algoritmo di ordinamento per selezione di massimo

L'algoritmo di ordinamento per selezione di massimo permette di ordinare un array in ordine crescente, che può contenere dati di tipo intero, carattere o stringhe di caratteri. Ha come dati di input un array, il suo size e come unico dato di output lo stesso array ordinato; questa tecnica è chiamata anche "in place" in quanto permette di ordinare un array senza l'utilizzo di ulteriori strutture dati. Questo algoritmo fa un numero di iterazioni che è uguale a size - 1, e ad ogni passo risolve il sotto problema di trovare l'elemento massimo e il suo indice.