home *** CD-ROM | disk | FTP | other *** search
/ ftp.disi.unige.it / 2015-02-11.ftp.disi.unige.it.tar / ftp.disi.unige.it / pub / .person / CataniaB / teach-act / esempi / Ordinamenti / quick.c < prev    next >
C/C++ Source or Header  |  1997-05-15  |  2KB  |  78 lines
  1. #include <stdio.h>
  2. #define MAX 20
  3.  
  4. void swap(int a[],int i,int j);
  5. /* scambia i valori delle due caselle a[i] e a[j] */
  6.  
  7. int  select(int a[],int inf,int med,int sup);
  8. /* partiziona a in inf-(med-1) (elementi piu' piccoli del pivot) 
  9.    e med+1-sup elementi piu' grandi del pivot */
  10.  
  11. void quick(int a[],int inf,int sup);
  12. /* ordina con l'algoritmo quicksort:
  13.    - seleziona il pivot 
  14.    - partiziona l'array a in elementi rispett. minori e maggiori del pivot
  15.    - ordina le due partizioni (lascia invariato il pivot)
  16. */
  17.  
  18.  
  19. void main(void)
  20. {
  21.  int a[MAX];
  22.  int i,n;
  23.  
  24.  printf("Dimensione?[Max:20]"); 
  25.  scanf("%d",&n);
  26.  
  27.  if (n>MAX) printf("\n Dimensione > %d",MAX);
  28.  else 
  29.  {
  30.    printf("Input?\n");
  31.    for(i=0;i<n;i++) scanf("%d",&a[i]);
  32.  
  33.    printf("Echo\n");
  34.    for(i=0;i<n;i++) printf(" %d",a[i]);
  35.  
  36.    quick(a,0,n-1);
  37.  
  38.    printf("\nOutput\n");
  39.    for(i=0;i<n;i++) printf(" %d",a[i]);
  40.  }
  41. }
  42.  
  43. void swap(int a[],int i,int j)
  44. {int temp;
  45.  
  46.  temp=a[i];
  47.  a[i]=a[j];
  48.  a[j]=temp;
  49. }
  50.  
  51. int select(int a[],int inf,int med,int sup)
  52.  {int last,i;
  53.     
  54.    last=inf;
  55.    swap(a,inf,med);            /* metto il pivot al posto di a[inf] */
  56.    for(i=inf+1;i<=sup;i++)
  57.      if (a[i]<a[inf]) swap(a,++last,i);   /* sposto  gli elementi minori del pivot piu' a sx possibile */ 
  58.    swap(a,inf,last);         /* risistemo il pivot */
  59.    return last;
  60.  }
  61.  
  62. void quick(int a[],int inf,int sup)
  63. {
  64.  int pivot,med;
  65.      
  66.   if (inf < sup) 
  67.    {
  68.      pivot=(inf+sup)/2;  /* con troncamento */
  69.      med=select(a,inf,pivot,sup); 
  70.      quick(a,inf,med-1);
  71.      quick(a,med+1,sup);
  72.  
  73.    } 
  74.  }
  75.  
  76.  
  77.  
  78.