a

ALGORITMI

Definizione di algoritmo

L’algoritmo è un insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in tempo finito.

Esempio di algoritmo

Mettiamo in evidenza i punti fondamentali che caratterizzano un algoritmo. (per esempio le istruzioni per l’utilizzo di un flacone di shampoo)

Passo 1: Bagna i capelli; Passo 2: Insapona i capelli; Passo 3: Risciacqua i capelli; Passo 4: Insapona i capelli; Passo 5: Risciacqua i capelli; Passo 6: Stop, lavaggio dei capelli terminato.

L’algoritmo d’ordinamento

Algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue.

Esistono vari tipi d’ordinamento

Selection sort;Insertion sort;Bubble sort;Quick sort;Merge sort;Heap sort;Countins sort;Bucket sort.

Selection Sort

L'algoritmo seleziona di volta in volta il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza da ordinare, che costituisce la parte restante dell'array (non dipende dall’input ma dalla dimensione dell’array).

Dovendo ordinare un array A di lunghezza n, si fa scorrere l'indice i da 1 a n-1 ripetendo i seguenti passi:

si cerca il più piccolo elemento della sottosequenza A[i..n];

si scambia questo elemento con l'elemento i-esimo

Esempio di Selection Sort

Insertion Sort

L'algoritmo solitamente ordina la sequenza sul posto. Si assume che la sequenza da ordinare sia partizionata in una sottosequenza già ordinata, all'inizio composta da un solo elemento, e una ancora da ordinare. Alla k-esima iterazione, la sequenza già ordinata contiene k elementi. In ogni iterazione, viene rimosso un elemento dalla sottosequenza non ordinata (scelto, in generale, arbitrariamente) e inserito (da cui il nome dell'algoritmo) nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.

Per fare questo, un'implementazione tipica dell'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito. Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

Esempio di Insertion Sort

Bubble Sort

 Il suo funzionamento è semplice: ogni coppia di elementi adiacenti della lista viene comparata e se essi sono nell'ordine sbagliato vengono invertiti. L'algoritmo scorre poi tutta la lista finché non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.

Esempio di bubble Sort

Quick Sort

L'idea base può esprimersi agevolmente in termini ricorsivi. Ad ogni stadio si effettua un ordinamento parziale di una sequenza di oggetti da ordinare. Assunto un elemento come perno dello stadio, si confrontano con esso gli altri elementi e si posizionano alla sua sinistra i minori e a destra i maggiori, senza tener conto del loro ordine. Dopo questo stadio si ha che il perno è nella sua posizione definitiva.

Esempio di Quick Sort

Merge Sort

Se la sequenza da ordinare ha lunghezza 0 oppure 1, è già ordinata. Altrimenti:

La sequenza viene divisa in due metà (se la sequenza contiene un numero dispari di elementi, viene divisa in due sottosequenze di cui la prima ha un elemento in più della seconda)

Ognuna di queste sottosequenze viene ordinata, applicando ricorsivamente l'algoritmo

Le due sottosequenze ordinate vengono fuse. Per fare questo, si estrae ripetutamente il minimo delle due sottosequenze e lo si pone nella sequenza in uscita, che risulterà ordinata

Esempio di Merge Sort

Heap Sort

In uno mucchio decrescente (utilizzato per ordinare ad esempio un array in senso crescente) ogni nodo padre contiene un valore maggiore o uguale a quello dei suoi due figli diretti, di conseguenza risulterà maggiore anche di tutti i nodi che si trovano nel sottoalbero di cui esso è la radice; questo non implica affatto che nodi a profondità maggiore contengano valori minori di quelli a profondità minore.

Esempio di Heap Sort

Counting Sort

L'algoritmo conta il numero di occorrenze di ciascun valore presente nell'array da ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari all'intervallo di valori. Il numero di ripetizioni dei valori inferiori indica la posizione del valore immediatamente successivo.

Si calcolano i valori massimo, , e minimo, , dell'array e si prepara un array ausiliario C di dimensione pari all'intervallo dei valori con C[i] che rappresenta la frequenza dell'elemento i+minimo nell'array di partenza A. Si visita l'array A aumentando l'elemento di C corrispondente. Dopo si visita l'array C in ordine e si scrivono su A, C[i] copie del valore i+minore .

Esempio di Counting Sort

Bucket Sort

L'intervallo dei valori, noto a priori, è diviso in intervalli più piccoli, detti cesti. Ciascun valore dell'array è quindi inserito nel cesto a cui appartiene, i valori all'interno di ogni cesto vengono ordinati e l'algoritmo si conclude con la concatenazione dei valori contenuti nei cesti. ____1° parte____ ____2°parte____