/* Esempio di quick sort e bubble sort 
   in questo programma c'e' un errore !!! */


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

#define NITEMS 3000


void bubble_sort(int*);
void quick_sort(int*,int,int);
void scambia(int *,int *);

void
main(int argc, char **argv)
{
int listab[NITEMS];
int listaq[NITEMS];

int ii;

for(ii=0;ii<NITEMS;ii++)
 {
  listab[ii]=listaq[ii]=rand();
 }

bubble_sort(listab);
quick_sort(listaq,0,NITEMS-1);
printf("\n");

#ifdef DEBUG
for(ii=0;ii<NITEMS;ii++)
 printf("%d -- %d\n",listab[ii],listaq[ii]);
#endif
}

void bubble_sort(int *a)
{
int ii;
int scambio=0;
int last=NITEMS;

while(!scambio)
 {
 printf(".");
 scambio=1;
 for(ii=1;ii<last;ii++)
  if(a[ii-1]>a[ii])
   {
    scambia(&a[ii],&a[ii-1]);
    scambio=0;
   }
 last--;
 }
 printf("\n");
}

void quick_sort(int *a, int sinistra, int destra)
{
 int ii,jj;
 int pivot;
 
 printf("#");

 pivot=a[sinistra];
 jj=sinistra+1;
 ii=destra;
 
 while(ii>jj)
 {
  while((a[jj]<=pivot)&&(jj<=destra))
   jj++;
  while((a[ii]>pivot)||(ii==jj))
   ii--;
  if(ii>jj)
   scambia(&a[ii],&a[jj]);
 }
 if(ii!=sinistra)
  scambia(&a[ii],&a[sinistra]);
 if(sinistra<(ii-1))
  quick_sort(a, sinistra, ii-1);
 if(destra>jj)
  quick_sort(a, jj, destra);
}

void scambia(int *a, int *b)
{
 int s;
 s=*a;
 *a=*b;
 *b=s;
}