*Algoritmi
Paola Disisto, Erika Griffini, Yris Noriega
*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;
1)
I dati da ordinare non possono essere tutti caricati in
memoria centrale;
Ordinamento esterno:
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
*Insertion sort
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 kesima 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.
*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 sort
Esempio: 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 sort
Esempio:
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