L’ALGORITMO
Un algoritmo è un procedimento
formale che risolve un determinato
problema attraverso un numero finito di
passi. Un problema risolvibile mediante
un algoritmo si dice computabile.
SELECTION SORT
Un algoritmo decisamente intuitivo ed estremamente semplice.
Nella pratica è utile quando l’insieme da ordinare è composto da
pochi elementi e dunque anche un algoritmo non molto efficiente
può essere utilizzato con il vantaggio di non rendere troppo
sofisticata la codifica del programma che lo implementa.
SELECTION SORT
Alla prima iterazione dell’algoritmo verrà selezionato l’elemento più
piccolo dell’intero insieme e sarà scambiato con quello che occupa la
prima posizione;
alla seconda iterazione è selezionato il secondo elemento più piccolo
dell’insieme ed è scambiato con l’elemento che occupa la seconda
posizione.
Si ripete fino ad aver collocato nella posizione corretta tutti gli n
elementi.
Questo tipo di ordinamento è il metodo da preferire
quando si devono ordinare file costituiti da record estremamente
grandi e da chiavi molto piccole.
SELECTION SORT
Esempio:
void selection_sort(int[] a, int n) {
int i=0;
for(i=0;i<n;i++) {
int j=0;
for(j=i+1;j<n;j++) {
if (a[i] < a[j]) {
int temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
INSERTION SORT
Ordinamento a inserimento, è un algoritmo relativamente
semplice per ordinare un array.
Ad ogni istante (iterazione), il vettore è costituito da una parte
iniziale ordinata (che aumenta di volta in volta) e da la parte
rimanente che contiene i valori da ordinare.
Per ogni valore ancora da inserire, viene fatta una ricerca binaria
nella parte ordinata del vettore e vengono spostati in avanti tutti
gli elementi per liberare la posizione.
Nella posizione liberata viene inserito il valore.
Molto vantaggioso per vettori quasi ordinati.
INSERTION SORT
Esempio:
}
void insertion_sort(int[] a,int n) {
}
int i=0,j=0;
for(i=1;i<n;i++) {
int x=a[i], s=1, d=i-1;
while(s<=d) {
int m=(s+d)/2;
if (x<a[m]) d=m-1;
else s=m+1;
}
for(j=i-1,j>=s;j--) a[j+1]=a[j];
a[s]=x;
BUBBLE SORT
L’algoritmo BUBBLE SORT si basa sull’idea di far emergere pian
piano gli elementi più piccoli verso l’inizio dell’insieme da ordinare
facendo sprofondare gli elementi maggiori verso il fondo.
La strategia adottata è quella di scorrere più volte la sequenza da
ordinare ed eventualmente scambiando la posizione di quelle
coppie di elementi non ordinate.
Dunque alla fine della prima scansione possiamo essere certi che
l’elemento massimo ha raggiunto la sua posizione corretta
nell’ultima posizione della sequenza.
La scansione successiva potrà fermarsi senza considerare l’ultimo
elemento dell’insieme e riuscendo così a collocare nella posizione
corretta (la penultima) il secondo elemento più grande
dell’insieme.
Si ripete fino ad aver completato l’ordinamento dell’intera
sequenza.
BUBBLE SORT
Esempio:
}
}
void bubble_sort(int[] a, int n) {
bool scambio=true;
int ultimo=n-1,i=0;
while (scambio) {
scambio=false;
for(i=0;i<ultimo;i++) {
if (a[i]>a[i+1]) {
int temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
scambio=true;
}
}
ultimo--;
QUICK SORT
Quicksort è un algoritmo di ordinamento ricorsivo.
La base del suo funzionamento è l'utilizzo ricorsivo della procedura
partition: preso un elemento da un array si pongono gli elementi
minori a sinistra rispetto a questo e gli elementi maggiori a destra.
Successivamente si procede in modo ricorsivo all'ordinamento
parziale delle sottosequenze di elementi rimasti non ordinati, fino al
loro esaurimento.
QUICK SORT
void sort(int[] array, int begin, int end) {
int pivot, l, r;
if (end > begin) {
pivot = array[begin];
l = begin + 1;
r = end+1;
while (l < r) {
if (array[l] < pivot) l++;
else {
r--;
swap(array[l], array[r]);
}
Quick Sort l--;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
} Swap
COUNTING SORT
il Counting sort è un algoritmo di ordinamento per valori numerici
interi.
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.
BUCKET SORT
Il Bucket sort è un algoritmo di ordinamento per valori numerici.
L'intervallo dei valori, noto a priori, è diviso in intervalli più piccoli,
detti bucket (cesto). Ciascun valore dell'array è quindi inserito nel
bucket a cui appartiene, i valori all'interno di ogni bucket vengono
ordinati e l'algoritmo si conclude con la concatenazione dei valori
contenuti nei bucket.
BUCKET SORT
Supponiamo che tutti i numeri sono ancora nell'intervallo 1..n, ma
che alcuni possono essere duplicati. Potremmo usare un array per
contare quante copie ci sono per ogni numero:
sort(int n, X[n])
{
int i,j, Y[n+1]
for (i = 0; i < n;
for (i = 0; i < n;
for (i = 0, j = 0;
while(Y[i]-- >
}
i++) Y[i] = 0;
i++) Y[X[i]]++;
i < n; i++)
0) X[j++] = i
HEAP SORT
Algoritmo di ordinamento iterativo.
L'algoritmo che ordina in senso crescente inizia creando uno heap
decrescente. Per ogni iterazione si copia la radice (primo elemento
dell'array) in fondo all'array stesso.
L'algoritmo poi ricostruisce uno heap di n-1 elementi spostando verso
il basso la nuova radice, e ricomincia con un altro scambio.
HEAP SORT
Esempio:
#include <stdlib.h>
#define MAX 20
int ArraySize, HeapSize, tot;
int left(int i) { return 2*i+1;}
int right(int i) { return 2*i+2;}
int p(int i) {return (i-1)/2;}
void swap(int A[MAX], int i, int j)
{int tmp = A[i];
A[i] = A[j];
A[j] =tmp;}
void Heapify(int A[MAX], int i);
void BuildHeap(int A[MAX]);
void HeapSort(int A[MAX]);
MERGE SORT
Il merge sort è un algoritmo di ordinamento molto intuitivo e
abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.
L'idea alla base del merge sort è il procedimento Divide et Impera,
che consiste nella suddivisione del problema in sottoproblemi via via
più piccoli.
Il merge sort opera quindi dividendo l'insieme da ordinare in due
metà e procedendo all'ordinamento delle medesime ricorsivamente.
Quando si sono divise tutte le metà si procede alla loro fusione
(merge appunto) costruendo un insieme ordinato.
MERGE SORT
Fase 1: divide
L'insieme di elementi viene diviso in 2 metà. Se l'insieme è
composto da un numero dispari di elementi, viene diviso in 2
sottogruppi dei quali il primo ha un elemento in meno del
secondo.
Fase 2: impera
Supponendo di avere due sequenze già ordinate. Per unirle,
l'algoritmo mergesort estrae ripetutamente il minimo delle due
sequenze in ingresso e lo pone in una sequenza in uscita.
MERGE SORT
void mergesort (int[] a, int left, int right) {
int center;
if (left < right) {
center = (left + right) / 2;
mergesort(a, left, center);
mergesort(a, center+1, right);
merge(a, left, center, right);