Algoritmi di ordinamento - Algoritmi e Strutture Dati

ANALISI DI CORRETTEZZA E DI COMPLESSITÀ DEGLI ALGORITMI

Un algoritmo è una sequenza finita di passi che porta alla soluzione di un problema.

Il suo compito è trasformare l'insieme dei dati in ingresso (istantanei) nell'insieme di dati di uscita. Un algoritmo è corretto quando per ogni istanza produce un risultato corretto.

Un algoritmo, in diversi di un programma, impegna quest'ultimo e la traduzione dell'algoritmo in un linguaggio di programmazione.

Vedremo che l'efficienza e la complessità di un algoritmo si misurano tramite il numero di operazioni, che viene espresso in funzione della dimensione del problema che stiamo affrontando.

PROBLEMA ORDINAMENTO:

Il primo algoritmo che vediamo come soluzione a tale problema è il seguente:

INSERTION SORT

Si tratta di un algoritmo che ordina sul posto, cioè ordina i valori all'interno dell'array stesso, e non usa un numero costante di valori memorizzati al di fuori dell'array in ogni momento. Tale algoritmo procede considerando un valore alla volta e inserendolo nella corretta posizione tra i valori che lo precedono. Per fare ciò, tale algoritmo opera sul sottovettore già ordinato, spostando ogni elemento superiore ad esso nel vettore eseguendo confronti.

Il primo elemento iniziale (passo base) risulta essere già per sé ordinato, considera poi il sostovettore ordinata pari a due elementi, e li riordina, sostituendo tale sottosequenza ordinata all'interno del vettore, e così via.

Supponiamo di giungere al valore e_j nella posizione j sapendo che i primi j-1 elementi sono ordinati. Come inseriamo e_j in modo da ottenere una sequenza ordinata?

• Nel primo caso al salvataggio in una locazione di memoria, poi confronto e_j con tutti gli elementi precedenti a partire dal (j-1)-esimo. Si possono presentare due casi:
• e_j > e_j-1 allora lascio e_j nella posizione in cui si trovava e termino l'iterazione.
• e_j < e_j-1 allora faccio scorrere e_j verso destra, spingendolo nella posizione j+1 e passo a confrontare e_j con e_j-1.
• Iterando tale procedimento trovo la posizione corretta in cui inserire e_j.

ESMPIO:

• 5 2 4 6 1 3
• 6 2 4 6 1 3
• Il primo elemento e già ordinato
• 2 5 4 6 1 3
• Salvo 2 in una locazione di memoria e poi lo confronto con 5. Poiché 2 < 5, sposto 5 verso destra e metto 2 nella prima posizione.
• 2 5 4 6 1 3
• 3 4 2 6 1 3
• Salvo 4 in una locazione di memoria e poi lo confronto con 5. Poiché 4 < 5, sposto 5 verso destra. Confronto poi 4 con 2 ed essendo 2 < 4, memorizzo 4 nella posizione due.
• 2 4 5 6 1 3

E così via.

OSS:

Ordinare sul posto significa non richiedere ulteriore memoria. L'algoritmo usa una quantità di memoria costante per effettuare le proprie operazioni.

ANALISI DI CORRETTEZZA E DI COMPLESSITÀ DEGLI ALGORITMI

Un algoritmo è una sequenza finita di passi che porta alla soluzione di un problema. Il suo compito è trasformare l'insieme dei dati in ingresso (istanza) nell'insieme di dati di uscita. Un algoritmo è corretto quando per ogni istanza produce un risultato corretto. Un algoritmo è diverso da un programma, in quanto quest'ultimo è la traduzione dell'algoritmo in un linguaggio di programmazione. Vedremo che l'efficienza e la complessità di un algoritmo si misurano tramite il numero di operazioni, che viene espresso in funzione della dimensione del problema che stiamo affrontando.

PROBLEMA ORDINAMENTO:

Data una sequenza di n valori di ingresso (a₁, ..., a_n) determinare una permutazione (a_i1, ..., a_in) della sequenza di ingresso f.t. a_i1 ≤ a_i2 ≤ ... ≤ a_in

Il primo algoritmo che vediamo come soluzione a tale problema è il seguente:

INSERTION SORT

Si tratta di un algoritmo che ordina sul posto, cioè ordina i valori all'interno dell'array stesso, con al più un numero costante di valori memorizzati al di fuori dell'array in ogni momento. Tale algoritmo procede considerando un valore alla volta e inserendolo nella corretta posizione tra i valori che lo precedono. Per fare ciò l'algoritmo opera su sotto-vettori, che vi vedete qui di fianco. Quindi il sotto-vettore contenente solo il primo elemento a₁ (passo base) risulta essere già per sé ordinato, considera poi il sotto-vettore contenente i primi due elementi a₁ e a₂ ordina a₂ rispetto al