[c] problema confronto algoritmi Ordinamento

[Rsk]

Ragazzi ho un problema con questo codice.. mi da dei valori decisamente elevati per quanto riguarda i tempi di esecuzione di alcuni algoritmi.. inoltre i numeri di scambi e confronti sembra troppo elevato..
siete in grado di aiutarmi?

Codice PHP:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

#define MAX_CIFRE 5
#define RADICE_SIZE 10
#define MAX 50000

typedef struct list_node *list_pointer;
typedef struct list_node{
           int chiave[MAX_CIFRE];
        list_pointer link;
        }lista;
list_pointer testa=NULL;

void copia(int a[],int l[],int);
void analisi(int a[],int n);
void lettura(int a[],int);
void selezione(int a[],int);
void inserzione(int a[],int,int);
void quick_sort(int a[],int,int);
void merge_sort(int a[],int,int);
void heap_sort(int a[],int);
void radix_sort(int a[],int);
void scambia(int*,int*);

int scambio,confronto;

main()
{
 int lista[MAX];
 int n,i,j,scelta=-1,temp,b=0,cont=0;
 puts("\n\n\t\t CONFRONTO ALGORITMI DI ORDINAMENTO");
 printf("\n\n  Numero elementi da ordinare(max %d) --> ", MAX);
 scanf("%d", &n);
 do
 {
  
  puts("\n\n\t DATI IN INPUT\n");
  puts("\t1 - Ordinato");
  puts("\t2 - Quasi Ordinato");
  puts("\t3 - Inversamante Ordinato");
  puts("\t4 - Casuale");
  puts("\t0 - Uscita");
  printf("  \tScelta: ");
  scanf("%d", &scelta);
  
  switch(scelta)
  {
   case 1:  for(i=1;i<=n;i++) lista[i]=i;
            break;

   case 2:  temp=n/10;
            for(i=0;i<n;i++){
                cont++;
                 if(cont==temp){b++;cont=0;}
                 if(b%2) lista[i]=rand()%n-1;
                 else lista[i]=i;
            }
            break;

   case 3:  for(i=0,j=n;i<n;i++,j--) lista[i]=j;
            break;

   case 4:  for(i=0;i<n;i++) lista[i]=rand()%n-1;
            break;

   default: if(scelta!=0){
                   puts("\n\tERRORE..");
               }
            break;
  }
  if(scelta) analisi(lista,n);
 }
 while(scelta);
}

void copia(int a[],int l[],int n)
{
 int i;
 for(i=0;i<n;i++) a[i]=l[i];
}

void analisi(int lista[],int n)
{
 clock_t start,end;
 int a[MAX];

 puts("\n\n\t\t  TABELLA CONFRONTO ALGORITMI ");
 puts("\n\n\tAlgoritmo \tScambi\tConfronti\t\tTempo");

 copia(a,lista,n);
 confronto=scambio=0;
 start=clock();
 selezione(a,n);
 end=clock();
 printf("\n\tSelezione \t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 copia(a,lista,n);
 start=clock();
 inserzione(a,1,n-1);
 end=clock();
 printf(" sec\n\tInserzione\t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 copia(a,lista,n);
 start=clock();
 quick_sort(a,0,n-1);
 end=clock();
 printf(" sec\n\tRapido    \t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 copia(a,lista,n);
 start=clock();
 merge_sort(a,0,n-1);
 end=clock();
 printf(" sec\n\tFusione   \t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 copia(a,lista,n);
 start=clock();
 heap_sort(a,n);
 end=clock();
 printf(" sec\n\tHeap      \t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 copia(a,lista,n);
 start=clock();
 radix_sort(a,n);
 end=clock();
 printf(" sec\n\tRadice    \t%3d\t%3d\t\t%3.3f",scambio,confronto,(end-start)/(float)CLOCKS_PER_SEC);

 puts(" sec\n\n\tINVIO PER CONTINUARE..");
 fflush(stdin);
 getchar();
}

void lettura(int a[],int n)
{
 int i;
 puts("\n\t\t\t\t LA LISTA CONTIENE ");
 for(i=0;i<n;i++)
  printf("%.4d ",a[i]);
 fflush(stdin);
 getchar();
}

/* SELEZIONE */
void selezione(int a[],int n)
{
 int i,j,min;
 for(i=0;i<n-1;i++)
 {
  min=i;
  for(j=i+1;j<n;j++)
  {
   confronto++;
      if(a[j]<a[min]) min=j;
  }
  scambia(&a[i],&a[min]);
 }
}

/* INSERZIONE */
void inserzione(int a[],int primo,int ultimo)
{
 int i,j,prossimo;
 for(i=primo;i<ultimo;i++)
 {
  prossimo=a[i];
  for(j=i-1;j>=primo && prossimo<a[j];j--)
  {
   scambio++;confronto++;
   a[j+1]=a[j];
  }
  scambio++;
  a[j+1]=prossimo;
 }
}

/* QUICK SORT */
void quick_sort(int a[],int u,int v)
{
 int perno(int a[],int,int);
 int p;
 confronto++;
 if(v==u) return;
 p=perno(a,u,v);
 
 if(u<p) quick_sort(a,u,p-1);
 confronto++;
 if(p<v) quick_sort(a,p+1,v);
}

int perno(int a[],int primo,int ultimo)
{
 int i=primo,j=ultimo+1,pivot=a[primo];

 do
 {
  do i++; while(a[i]<pivot && i<j);
  do j--; while(a[j]>pivot && j>primo);
  if(i<j) {scambia(&a[i],&a[j]);}
 }
 while(i<j);
 scambia(&a[primo],&a[j]);
 return j;
}

void scambia(int *a1,int *a2)
{
 scambio++;
 int park;
 park=*a1;
 *a1=*a2;
 *a2=park;
}

/* MERGE SORT */
void merge_sort(int a[],int lower,int upper)
{
 void merge(int a[],int,int,int);
 int medium;
 confronto++;
 if(lower<upper)
 {
  medium=(lower+upper)/2;
  merge_sort(a,lower,medium);
  merge_sort(a,medium+1,upper);
  merge(a,lower,medium,upper);
 }
}

void merge(int a[],int i,int m,int n)
{
 int ordinata[MAX],j,k,t,inizio=i;

 j=m+1;
 k=i;
 while(i<=m && j<=n)
 {
  confronto++;
  if(a[i]<a[j])
          ordinata[k++]=a[i++];
  else
          ordinata[k++]=a[j++];
 }

 if(i>m)
     for(t=j;t<=n;t++) ordinata[k+t-j]=a[t];
 else
   for(t=i;t<=m;t++) ordinata[k+t-i]=a[t];

 for(t=inizio;t<=n;t++) {scambio++;a[t]=ordinata[t];}
}

/* HEAP SORT */
void heap_sort(int a[],int n)
{
 void adatta(int a[],int,int);
 int i,park;
 for(i=n/2;i>0;i--) adatta(a,i,n);
 for(i=n-1;i>0;i--)
 {
  scambio++;
  park=a[1];
  a[1]=a[i+1];
  a[i+1]=park;
  adatta(a,1,i);
 }
}

void adatta(int a[],int radice,int n)
{
 int figlio,temp,chiave;

 temp=a[radice];
 chiave=a[radice];
 figlio=2*radice;
 while(figlio<=n)
 {
  confronto++;
  if((figlio<n) && a[figlio]<a[figlio+1])
      figlio++;
  confronto++;
  if(chiave>a[figlio])
      break;
  else
  {
   scambio++;
   a[figlio/2]=a[figlio];
   figlio*=2;
  }
 }
 scambio++;
 a[figlio/2]=temp;
}

/* RADIX SORT */
void radix_sort(int a[],int n)
{
 list_pointer crea_lista(list_pointer,int);
 list_pointer radice_sort(list_pointer);
 int i;
 for(i=0;i<n;i++)
  testa=crea_lista(testa,a[i]);
 testa=radice_sort(testa);
}

list_pointer crea_lista(list_pointer inizio,int q)
{
 list_pointer temp,succ;
 int j,r;
 succ=inizio;

 if((temp=(list_pointer)malloc(sizeof(lista)))==NULL)
      {puts("memory error");exit(1);}
  temp->link=NULL;
  for(j=MAX_CIFRE-1;j>=0;j--)
  {
   r=q%10;
   q=q/10;
   temp->chiave[j]=r;
  }
  if(!inizio)
      return(temp);
  while(succ->link)
      succ=succ->link;
  succ->link=temp;
  return(inizio);
}

list_pointer radice_sort(list_pointer ptr)
{
 list_pointer davanti[RADICE_SIZE],dietro[RADICE_SIZE];
 int i,j,cifra;

 for(i=MAX_CIFRE-1;i>=0;i--)
 {
  for(j=0;j<RADICE_SIZE;j++) davanti[j]=dietro[j]=NULL;
  while(ptr)
  {
   cifra=ptr->chiave[i];
   if(!davanti[cifra])
       davanti[cifra]=ptr;
   else
       dietro[cifra]->link=ptr;
   dietro[cifra]=ptr;
   ptr=ptr->link;
  }
  ptr=NULL;
  for(j=RADICE_SIZE-1;j>=0;j--)
  {
      if(davanti[j])
   {
    dietro[j]->link=ptr;
    ptr=davanti[j];
   }
  }
 }
 return ptr;
}