Definizione di algoritmo:
Un algoritmo è un procedimento che risolve un determinato problema
attraverso un numero finito di passi. Un problema risolvibile mediante
un algoritmo si dice computabile.
Tutti i tipi di algoritmo
Selection Sort:
void selsort(int x[ ], int y) {
int z=0;
for (z=0;z<n;z++) {
int y=0;
for (y=z+1;y<n;y++) {
if (x[y] < x[y]) {
int t=x[y];
x[y]=x[z];
x[z]=t;
}
}
}
alla prima iterazione 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 è viene scambiato con l’elemento che occupa la seconda posizione.
Si ripete fino ad aver collocato nella posizione corretta tutti gli n elementi.
Inserction Sort:
void inssort(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;
}
}
Ad ogni iterazione, il vettore è costituito da una parte iniziale
ordinata 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 una posizione
Nella posizione liberata viene inserito il valore.
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:
void sort(int a[ ], int inizio, int fine) {
int x, y, z;
if (fine >inizio) {
x = a [inizio];
y= inizio + 1;
z= fine+1;
while (y < z) {
if (a [y] < x) y++;
else {
r--;
swap(a[y], a[z]);
}
void swap(int & x, int & y) {
int temp=x;
x=y;
y=temp;
}
Assunto un elemento come perno, 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. Successivamente si procede in modo ricorsivo all'ordinamento parziale
delle sottosequenze di elementi rimasti non ordinati, fino al loro esaurimento.
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)) {
if (x[i] <= x[j]){
void mergesort (int[] a, int left, int right) {
y[k]=a[i];
int center;
i=i + 1;
if (left < right) {
} else {
center = (left + right) / 2;
y[k] = x[j];
mergesort(a, left, center);
j=j + 1;
mergesort(a, center+1, right);
}
merge(a, left, center, right);
k=k + 1;
}
}
for (k =left ;k<right;k++) {
a[k] = b[k - left];
}
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. Supponendo di avere due sequenze già ordinate. Per unirle,
mergesort estrae ripetutamente il minimo delle due sequenze in ingresso e lo pone in
una sequenza in uscita.
Heap Sort:
void 1_Heap(t_id_tab a[], int n, int lh, int i){
int s, d, max;
s = 2*i + 1;
d = 2*i + 2;
if ((s < lh) && (a[s] > a[i]))
max = s;
Else
max = i;
if ((d < lh) && (a[d].chaive > a[max].chiave))
max = d;
if (max != i){ temp = a[i]; a[i] = a[max];
a[max] = temp;
1_Heap(a, n, lh, max);
void 2_Heap(t_id_tab a[], int n){
int i;
for(i = n/2 - 1; i >= 0; i--)
1 Heap(a, n, lh, i);
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:
Per ogni elemento x dell'insieme da ordinare si determinano quanti elementi sono
minori di x, si usa questa informazione per assegnare ad x la sua posizione finale nel
vettore ordinato. Se, ad esempio, vi sono 8 elementi minori di x, allora x andrà messo
nella posizione 9 bisogna fare attenzione al caso in cui vi siano elementi coincidenti. In
questo caso infatti non vogliamo assegnare a tutti la stessa posizione.
void counting_sort(int* A, int Alen, int* B, int k){
int i;
int C[k];
for(i=0; i<k; i++)
C[i] = 0;
int j;
for(j=0; j<Alen; j++)
C[A[j]] = C[A[j]]+1;
for(i=1; i<k; i++)
C[i] = C[i]+C[i-1];
for (j=Alen-1; j>=0; j--){
B[C[A[j]]-1] = A[j];
C[A[j]] = C[A[j]]-1;
}
}
Bucket Sort:
Bucket sort suppone che l’input sia generato da un processo casuale che distribuisce
gli elementi uniformemente nell’intervallo [0, 1[. Il concetto che sta alla base
dell’algoritmo è quello di dividere l’intervallo [0, 1[ in n sottointervalli della stessa
dimensione, detti bucket, nei quali vengono distribuiti gli n valori di input. A questo
scopo lo pseudocodice che definisce l’algoritmo suppone che l’input sia un array A di n
elementi e richiede un array ausiliario B[0...n−1] di liste concatenate (bucket).
L’algoritmo procede semplicemente ordinando i valori in ogni bucket tramite un
ordinamento di tipo insertion sort. L’output viene infine prodotto concatenando in
ordine i vari bucket in un array.
int main() {
#include <stdio.h>
int array[] = {1,3,4,6,4,2,9,1,2,9};
void bucketSort(int array[ ], int n) {
int n = 10;
int i, j;
int i;
int count[n];
for (i = 0;i < n;i++) {
for(i=0; i < n; i++) {
printf("%d ", array[i]);
count[i] = 0;
}
}
printf("\n");
for(i=0; i < n; i++) {
bucketSort(array, n);
(count[array[i]])++;
for (i = 0;i < n;i++) {
}
printf("%d ", array[i]);
for(i=0,j=0; i < n; i++) {
}
for(; count[i]>0; (count[i])--) {
printf("\n");
array[j++] = i;
return 0;