ORDINAMENTO

Esistono moltissimi algoritmi che permettono di ordinare cose. Io ho affronterò
i più famosi. 

SCAMBIO

Il più semplice di tutti è il bubble sort. Si comporta esattamente come noi
quando mettiamo a posto un mazzo di carte. Prendiamo una singola carta e la 
confrontiamo con tutte quelle già messe per trovare la posizione esatta.

Questo algoritmo fa parte degli algoritmi di scambio poiché si basa su 
sostituzioni continue di dati.

void bubble_sort(TYPE *array, int count) {
 register int a,b;
 TYPE tmp;

 for(a=0;a<count;a++) {
  for(b=count-1;b>=a;--b) {
   if(array[b-1]>array[b]) {
    tmp=array[b-1];
    array[b-1]=array[b];
    array[b]=tmp;
   }
  }
 }
}

Sequenza:

DCAB
ADCB
ABDC
ABCD

Numero di confronti effettuati: 1/2(n^2 - n)

Modifica semplice al bubble sort è quella che genera il shaker sort. 
Ordinare in entrambi i sensi. Non si ottiene alcun miglioramento di 
prestazioni.

void shaker_sort(TYPE *array, int count) {
 register int a,b;
 TYPE tmp;

 do {
  b=0;
  for(a=count-1;a>0;--a) {
   if(array[a-1]>array[a]) {
    tmp=array[a-1];
    array[a-1]=array[a];
    array[a]=tmp;
    b=1;
   }
  }

  for(a=1;a<count;++a) {
   if(array[a-1]>array[a]) {
    tmp=array[a-1];
    array[a-1]=array[a];
    array[a]=tmp;
    b=1;
   }
  }
 } while(b);
}

SELEZIONE

Altra famiglia di algoritmi sono quelli di selezione detto così perché 
selezionano l'elemento più basso o lo scambia col primo elemento. Così via
per i prossimi n-1 casi.

Si ottiene un numero di confronti pari a 1/2(n^2-n)

con un codice no ricorsivo come questo:

void selection_sort(TYPE *array, int count) {
 register int a,b,c;
 int d;
 TYPE tmp;

 for(a=0;a<count-1;++a) {
  d=0;
  c=a;
  tmp=array[a];
  for(b=a+1;b<count;++b) {
   if(array[b]<tmp) {
    c=b;
    tmp=array[b];
    d=1;
   }
  }
  if(d) {
   array[c]=array[a];
   array[a]=tmp;
  }
 }
}

BDAC
ADBC
ABDC
ABCD

Molto più veloce nel caso migliore, ma nel caso peggiore ruotiamo sempre
intorno ai casi del bubble sort.

INSERIMENTO

Prende 2 elementi. Li ordina fra loro. Aggiunge un 3° e lo ordina. Così per
tutti gli elementi.

Si migliora il caso migliore e il caso medio ma il numero dei confronti ruota
intorno a 1/2(n^2-n)

void insertion_sort(TYPE *array, int count) {
 register int a,b;
 TYPE tmp;

 for(a=1;a<count;++a) {
  tmp=array[a];
  for(b=a-1;b>=0 && tmp<array[b];b--) array[b+1]=array[b];
  array[b+1]=tmp;
 }
}

DCAB
CDAB
ACDB
ABCD

ALGORITMI AVANZATI

Per migliorare drasticamente le prestazioni si può usare uno shell sort.
I confronti diminuiscono a n^(1,2).

Data una chiave di numeri lui segue le sostituzioni in base a quello.
Una chiave può essere 5 3 2 1 ad esempio. Tutti i numeri devono essere 
discendenti e devono essere minori della lunghezza della stringa.

TYPE *shell_sort_init_key(int l_chiave) {
 register int a;
 TYPE *chiave;
 if((chiave=(TYPE *)malloc(l_chiave*sizeof(TYPE)))==NULL) return NULL;
 
 for(a=0;a<l_chiave;a++) {
  if(a) chiave[a]=chiave[a-1] + 2;
  else  chiave[a]=1;
 }
 return chiave;
}

/* Ricerca */
void shell_sort(TYPE *array, int count, TYPE *chiave, int l_chiave) {
 register int i,j,gap,k;
 TYPE x;

 for(k=0;k<l_chiave;k++) {
  gap=chiave[k];
  for(i=gap;i<count;++i) {
   x=array[i];
   for(j=i-gap;x<array[j] && j>=0; j=j-gap) array[j+gap]=array[j];
   array[j+gap]=x;
  }
 }
}

/*** ALGORITMI DI RICORRENZA ***/

/* Counting sort */
void counting_sort(TYPE *array, int count) {
 register int x;
 TYPE *c,*b,k;

 for(x=0;x<count;x++) if(k<array[x]) k=array[x];
 if((c=(TYPE *)malloc(k*sizeof(TYPE)))==NULL)     return;
 if((b=(TYPE *)malloc(count*sizeof(TYPE)))==NULL) {free(c); return;}
 for(x=0;x<count;x++)  c[x]=b[x]=0;

 for(x=0;x<count;x++)    c[array[x]-1]++;
 for(x=1;x<k;x++)        c[x]+=c[x-1];
 for(x=count-1;x>-1;--x) b[(c[array[x]-1]--)-1]=array[x];
 for(x=0;x<count;x++)    array[x]=b[x];
 free(c);
 free(b);
}

/* Funzione di heapsort */
void heap_sort(TYPE *array,int count) {
 register int i;

 heap_build(array, count);

 for (i=count-1; i>0; i--) {
  TYPE tmp;
  tmp=array[i];
  array[i]=array[0];
  array[0]=tmp;
  heap_heapify(array, 0, --count);
 }
}

L'algoritmo più veloce mai creato è il QUICK SORT. Algoritmo ricorsivo di
scambio.

- Confronti:    n log n
- Sostituzione: n/6 log n

void quick_sort_recursive(TYPE *array, int sx, int dx) {
 register int i,j;
 TYPE x,y;

 i=sx;
 j=dx;
 x=array[(sx+dx)/2];

 do {
  while(array[i]<x && i<dx) i++;
  while(x<array[j] && j>sx) j--;

  if(i<=j) {
   y=array[i];

   array[i]=array[j];
   array[j]=y;
   i++;
   j--;
  }
 } while(i<=j);

 if(sx<j) quick_sort_recursive(array,sx,j);
 if(i<dx) quick_sort_recursive(array,i,dx);
}

/* Merge Sort */
void merge_sort_union(TYPE *array, int inizio, int mezzo, int fine) {
 int i,j,k;
 TYPE *tmp;

 if((tmp=(TYPE *)malloc(sizeof(TYPE)*(fine-inizio+1)))==NULL) return;

 i=inizio;
 j=mezzo+1;
 k=0;
 while(i<=mezzo && j<=fine) {
  if(array[i]<array[j]) tmp[k++]=array[i++];
  else                  tmp[k++]=array[j++];
 }
 while(i<=mezzo) tmp[k++]=array[i++];
 while(j<=fine)  tmp[k++]=array[j++];
	
 for(i=inizio,j=0;i<=fine && j<k;i++,j++) array[i]=tmp[j];
}

void merge_sort_recursive(TYPE *array, int inizio, int fine) {
 
 if(inizio<fine) {
  merge_sort_recursive(array, inizio, (inizio+fine)/2);
  merge_sort_recursive(array, ((inizio+fine)/2)+1, fine);
 }

 merge_sort_union(array, inizio, (inizio+fine)/2, fine);
}