Paola Disisto, Erika Griffini, Yris Noriega

*Algoritmi

*Definizione*Insieme ordinato di operazioni non ambigue ed effettivamente computabili che, quando eseguito, produce un risultato e si arresta in un tempo finito;

*Un algoritmo deve essere quindi:Finito → Costituito da un numero limitato di passi;

Definito → Ogni istruzione deve consentire un’interpretazione univoca;

Eseguibile → Cioè la sua esecuzione deve essere possibile con gli strumenti di cui si dispone;

Deterministico → Ad ogni passo deve essere definita una ed una sola operazione successiva;

*Tipologie*Ordinamento interno ed esterno;

*Ordinamento per confronti scambi e digitale;

*Ordinamento adattivo;

*Selection sort;

*Insertion sort;

*Quick sort;

*Merge sort;

*Bubble sort;

*Heap sort;

*Counting sort;

*Tipi di ordinamento*Ordinamento interno:

1. I dati da ordinare sono tutti contenuti nella memoria centrale;

2. Accesso diretto ai vari elementi;

*Ordinamento esterno:

1. I dati da ordinare non possono essere tutti caricati in memoria centrale;

2. Occorre agire direttamente sui dati memorizzati in file;

3. Accesso tipicamente sequenziale;

*Selection sort*È un algoritmo di ordinamento di tipo non adattivo, ossia il

suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array;

Esempio:

procedure SelectionSort(a: lista dei numeri da ordinare);

for i = 1 to n – 1

posmin ← i

for j = (i + 1) to n

if a[j] < a[posmin]

posmin ← j

aus ← a[i]

a[i] ← a[posmin]

a[posmin] ← aus

*Selection sort*L'algoritmo seleziona di volta in volta il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata;

*La sequenza viene suddivisa in due parti: la sotto sequenza ordinata, che occupa le prime posizioni dell'array, e la sotto sequenza da ordinare, che costituisce la parte restante 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:

1. Si cerca il più piccolo elemento della sotto sequenza A[i..n];

2. Si scambia questo elemento con l'elemento i-esimo;

*Insertion sort*È un algoritmo in place , cioè ordina l'array senza

doverne creare una copia, risparmiando memoria;

Esempio:

function insertionSort(array A)

for i ← 1 to length[A] do

value ← A[i]

j ← i-1

while j >= 0 and A[j] > value do

A[j + 1] ← A[j]

j ← j-1

A[j+1] ← value

*L'algoritmo solitamente ordina la sequenza sul posto. Si assume che la sequenza da ordinare sia partizionata in una sotto sequenza 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 sotto sequenza non ordinata (scelto, in generale, arbitrariamente) e inserito (da cui il nome dell'algoritmo) nella posizione corretta della sotto sequenza 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.

*Insertion sort

*Quick sort*È un algoritmo di ordinamento ricorsivo in place; la sua funzione è di

prendere un elemento da una struttura dati e pone gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra;

Esempio:

Procedure Quicksort(A)

Input A, vettore a1, a2, a3 .. an

begin

if n ≤ 1 then return A

else

begin

scegli un elemento pivot ak

calcola il vettore A1 dagli elementi ai di A tali che i ≠ K e ai ≤ ak

calcola il vettore A2 dagli elementi aj di A tali che j ≠ K e aj > ak

A1 ← Quicksort(A1)

A2 ← Quicksort(A2)

return A1 · (ak) · A2;

*Merge sort*L’algoritmo funzione nel seguente modo → Divide et impera:

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

Altrimenti:

1.La sequenza viene divisa (Divide) in due metà: Se la sequenza contiene un numero dispari di elementi, viene divisa in due sotto sequenze di cui la prima ha un elemento in più della seconda;

2.Ognuna di queste sotto sequenze viene ordinata, applicando ricorsivamente l'algoritmo(impera);

3.Le due sotto sequenze ordinate vengono fuse (combina). Per fare questo, si estrae ripetutamente il minimo delle due sotto sequenze e lo si pone nella sequenza in uscita, che risulterà ordinata.

*Merge sort*Implementazione:

1.Top-Down, che è quella presentata in questa pagina. Opera da un insieme  e lo divide in sotto insiemi  fino ad arrivare all'insieme contenente un solo elemento, per poi riunire le parti scomposte;

2.Bottom-Up, che consiste nel considerare l'insieme  come composto da un vettore di  sequenze. Ad ogni passo vengono fuse due sequenze.

*Esempio: (Tecnica del Top - down)

function mergesort (a[], left, right)

if left < right then

center ← (left + right) / 2

mergesort(a, left, center)

mergesort(a, center+1, right)

merge(a, left, center, right)

*Bubble sort*È un algoritmo di ordinamento dei dati: 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:

procedure BubbleSort( A : lista di elementi da ordinare)

alto ← lenght(A) - 1

while (alto > 0) do

for i ← 0 to alto do

if (A[i] > A[i + 1]) then //scambiare il '>' con '<' per ottenere

swap ( A[i], A[i+1] ) // un ordinamento decrescente

alto ← alto - 1

*Bubble sort*È un algoritmo iterativo, ossia basato sulla

ripetizione di un procedimento fondamentale;

*La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito → Cioè si scorra l'array a partire dall'inizio in avanti, o a partire dal fondo all'indietro, è irrilevante; nel seguito ipotizzeremo che lo si scorra partendo dall'inizio.

1. Se i numeri sono in tutto N, dopo N-1 iterazioni si avrà la garanzia che l'array sia ordinato;

2. Alla iterazione i-esima, le ultime i-1 celle dell'array ospitano i loro valori definitivi, per cui la sequenza di confronti può essere terminata col confronto dei valori alle posizioni N-1-i e N-i.

*Heap sort*È un algoritmo di ordinamento iterativo ed in-place,

che si basa su strutture dati ausiliarie.

*Per eseguire l'ordinamento, utilizza una struttura chiamata heap (mucchio) → Rappresentabile con un albero binario in cui tutti i nodi seguono una data proprietà, detta priorità. Esso è completo almeno fino al penultimo livello dell'albero e ad ogni nodo corrisponde uno ed un solo elemento.

*Struttura molto usata, in particolare, per l'ordinamento di array.

*Heap sortEsempio: Triangolo di Tartaglia

#include

*Counting sort*È un algoritmo di ordinamento per valori numerici interi con complessità lineare. L'algoritmo si basa sulla conoscenza a priori dell'intervallo in cui sono compresi i valori da ordinare;

*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.

*Counting sortEsempio:

Counting-sort(A,B,k)

for i ← 1 to k

do C[i]← 0

for j ← 1 to lenght[A]

do C[A[j]] ← C[A[j]] + 1

► C[i] now contains the number of elements equal to i.

for i ← 2 to k

do C[i]← C[i]+ C[i - 1]

► C[i] now contains the number of elements less than or equal to i.

for j ← lenght[A] down to 1

do B[C[A[j]]] ← A[j]

C[A[j]] ← C[A[j]] - 1

*Fine