ALGORITMI DI
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.
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.
SELECTION SORT
void selsort(int x[ ],
Alla prima iterazione verrà selezionato
int y) {
l’elemento più piccolo dell’intero
int z=0;
insieme e sarà scambiato con quello
for (z=0;z<n;z++) {
che occupa la prima posizione.
int y=0;
Alla seconda iterazione è selezionato il
for (y=z+1;y<n;y++)
{if (x[y] < x[y]) {
secondo elemento più piccolo
int t=x[y];
dell’insieme è viene scambiato con
x[y]=x[z];
l’elemento che occupa la seconda
x[z]=t;
posizione.
}
Si ripete fino ad aver collocato nella
}
posizione corretta tutti gli n elementi.
}
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.
INSERTION SORT
void inssort(int a[ ] ,int n) { Ad ogni iterazione, il vettore è
int i=0,j=0;
costituito da una parte iniziale
for (i=1;i<n;i++) {
ordinata e da la parte rimanente
int x=a[i], s=1, d=i-1;
che contiene i valori da ordinare.
while (s<=d) {
Per ogni valore ancora da inserire,
int m=(s+d)/2; if (x<a[m]) d=m-1;
viene fatta una ricerca binaria
else s=m+1;
nella parte ordinata del vettore e
}
for (j=i-1,j>=s;j--) a[j+1]=a[j]; vengono spostati in avanti tutti gli
a[s]=x;
elementi per liberare una posizione
}
Nella posizione liberata viene
}
inserito il valore.
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.
BUBBLE SORT
void bubbsort(int x[ ], int
y) {
bool scambio=true;
int ultimo=y-1,i=0;
while (scambio) {
scambio=false;
for (i=0;i<ultimo;i++) {
if ( x[i]> x[i+1]) {
int t= x[i];
x[i]=x[i+1];
x[i+1]=t;
scambio=true;
}
}
ultimo --;
}
}
L’algoritmo BUBBLE SORT
(ordinamento a bolle) so 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: un po’ come le
bollicine in un bicchiere di acqua
gassata da qui il nome di
ordinamento a bolle.
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.
QUICK SORT
void sort(int a[ ], int inizio, int fine)
{
int x, y, z;
Assunto un elemento come perno, si
if (fine >inizio) {
x = a [inizio];
confrontano con esso gli altri elementi e si
y= inizio + 1;
posizionano alla sua sinistra i minori e a
z= fine+1;
while (y < z) {
destra i maggiori, senza tener conto del loro
if (a [y] < x) y++;
ordine. Dopo questo stadio si ha che il perno
else {
r--;
è nella sua posizione
swap(a[y], a[z]);
}
definitiva. Successivamente si procede in
void swap(int & x, int & y) {
modo ricorsivo all'ordinamento parziale delle
int temp=x;
sottosequenze di elementi rimasti non
x=y;
y=temp;
ordinati, fino al loro esaurimento.
}
MERGE SORT
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.
MERGE SORT
void mersort (int x[ ], int sinistra,
int centro, int destra)
int i = sinistra, j=centro+ 1,k=0;
int y[ ];
while ((i <= centro) && (j <= destra))
{
void mergesort (int[] a, int
if (x[i] <= x[j]){
left, int right) {
y[k]=a[i];
i=i + 1;
int center;
} else {
if (left < right) {
y[k] = x[j];
center = (left + right) / 2;
j=j + 1;
}
mergesort(a, left, center);
k=k + 1;
mergesort(a, center+1, right);
}
for (k =left ;k<right;k++) {
merge(a, left, center, right);
a[k] = b[k - left];}
}
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.
HEAP SORT
void HeapSort(int a[ ], int n){
int i;
int lh = n;
Costruisci_Heap(a, n);
for(i = n-1; i > 0; i--){
temp = a[i];
a[i] = a[0];
a[0] = temp;
lh--;
Rendi_Heap(a, n, lh, 0); }
}
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.
COUNTING SORT
void counting_sort(int* A,int Alen,int* B,int k){
int i;
Per ogni elemento x dell'insieme da
int C[k];
for(i=0; i<k; i++)
ordinare si determinano quanti elementi
C[i] = 0;
sono minori di x, si usa questa
int j;
informazione per assegnare ad x la sua
for(j=0; j<Alen; j++)
posizione finale nel vettore ordinato. Se,
C[A[j]] = C[A[j]]+1;
ad esempio, vi sono 8 elementi minori di
for(i=1; i<k; i++)
C[i] = C[i]+C[i-1];
x, allora x andrà messo nella posizione 9
for (j=Alen-1; j>=0; j--){ bisogna fare attenzione al caso in cui vi
B[C[A[j]]-1] = A[j];
siano elementi coincidenti. In questo
C[A[j]] = C[A[j]]-1;
caso infatti non vogliamo assegnare a
}
}
tutti la stessa posizione.
BUCKET 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.
BUCKET SORT
void bucketSort(int array[ ], int n) {
int i, j;
Il concetto che sta alla base
int count[n];
for(i=0; i < n; i++) {
dell’algoritmo è quello di dividere
count[i] = 0;
}
l’intervallo in n sottointervalli della
for(i=0; i < n; i++) {
stessa dimensione, detti bucket, nei
(count[array[i]])++; }
for(i=0,j=0; i < n; i++) {
quali vengono distribuiti gli n valori
for(; count[i]>0; (count[i])--) {
di input. A questo scopo lo
array[j++] = i;
}}}
pseudocodice che definisce
int main() {
l’algoritmo suppone che l’input sia
int array[] = {1,3,4,6,4,2,9,1,2,9};
un array A di n elementi e richiede
int n = 10; int i;
un array ausiliario B[0...n−1] di liste
for (i = 0;i < n;i++) {
printf("%d ", array[i]); }
concatenate (bucket). L’algoritmo
printf("\n");
procede semplicemente ordinando i
bucketSort(array, n);
for (i = 0;i < n;i++) {
valori in ogni bucket tramite un
printf("%d ", array[i]); }
ordinamento di tipo insertion sort.
printf("\n");