optimization.c

A order algoritm comparison by the C time(). Comparison beetwen : insort,selection sort,mergesort,

#include "in.h"
#include "func.h"
/*Il mergesort e la gran parte degli algoritmi ricorsivi si puo migliorare
  gestendo problemi di piccole dimensione in modo speciale.La ricorsione garantisce che
  il metodo speciale verra'  usato un gran numero di volte ,quindi migliorare la gestione
  dei problemi piccoli ha un impatto significativo sulle prestazioni dell intero algoritmo.
  Usare quindi l'insertion sort per i file di piccole dimesioni migliora le prestazioni dell
  algoritmo del 10-15 per cento.
  Un secondo miglioramento ragionevole per il mergesort e' quello di eliminare il tempo
  richiesto dalla copia nel file ausiliario durante la fusione.
  Per fare cio organizziamo le chiamate ricorsive in modo tale che la computazione scambi
  i ruoli dell'array di input e dell' array ausiliario a ogni livello.
  Un modo di procedere e' quello di implementare due versioni delle routine, la prima
  con ingresso aux e uscita in a , e la seconda con ingresso a e uscita in aux e quindi fare
  in modo che le due versioni si chiamino a vicenda.
  Mostro un metodo alternativo di procedere nel codice 


  che esegue all inizio una copia dell'array quindi usa il programma 




  e scambia gli argomenti nelle chiamate ricorsive per eliminare l'operazione di 
  copia di array. Al suo posto prendiamo invece l'array combinato e lo copiamo
  alternativamente nell' array aux e in quello di input.)
  Questa tecnica elimina la copia dell' array a costo di reinserire nel
  ciclo interno i test che verificano se i due array sono esauriti. */

void mergeAB(int c[],int a[], int N,int b[],int M) {
int i,j,k;
for (i=0,j=0,k=0;k<N+M;k++) 
{
  if (i==N) { c[k]= b[j++]; continue; }
  if (j==M) {  c[k]= a[i++]; continue; }
 c[k]=(a[j]<b[j]) ? a[i++]: b[j++] ; }}

void optimizationAB(int a[],int l,int r) {
 int i,aux[r];
 for (i=1;i<=r;i++) aux[i]=a[i];
 optimizationABr(a,aux,l,r);}

void optimizationABr(int a[],int b[],int l,int r)
{
 int m=(l+r)/2;
 if ((r-l)<=10){ insort_mod(a,l,r); return ;}
 optimizationABr(b,a,l,m);
 optimizationABr(b,a,m+1,r);
 mergeAB(a+l,b+l,m-l+1,b+m+1,r-m); }

 

/*------------------------------------
 * Algoritmo di riordino merge sort
 */

void insort_mod(int a[],int inf ,int sup)
{
		int prov;
		int i,j;
		for (j=inf+1;j<=sup; j++)
		{
			prov=a[j];
			i=j-1;
			while (i>=inf && a[i]> prov)
			{
				a[i+1]=a[i];
				i=i-1;
			}
			a[i+1]=prov;
		}
}
				
void optim(int A[],int length) 
 {
	 if (length<80) insort (A,length) ;
	 else sort_modifica (A,0,length-1);
 }

void sort_modifica(int A[], int min, int max) {
	   if (min < max) {
           int Mid = (min+max)/2;
           sort_modifica(A,min,Mid);
           sort_modifica(A,Mid+1,max);
           merge_modifica(A,min,Mid,max);
			          }
}

int merge_modifica(int A[], int p, int q,int r) {

       int B[r-p+1];
        int i = p;
        int j = q+1;
        int k = 0;
	if ((r-p)<80) { insort_mod(A,p,r); return;}
	else {
		

        while ( (i <= q) && (j <= r) ) {
                if (A[i] < A[j])
                        B[k] = A[i++];
                else 
                        B[k] = A[j++];
                k++;
        }

        while (i <= q)
                B[k++] = A[i++];
        
        while (j <= r)
                B[k++] = A[j++];
        

} 

for (i=0; i<r-p+1; i++)
                A[p+i] = B[i];
		
} /* merge */