/***     ALGORITMI DI ORDINAMENTO      ***/ 


#include <stdio.h>
#include <stdlib.h> // prototipo di rand() 
#include <time.h>  //  prototipi clock(), time(), ecc. 




#define MAX 500000  // lunghezza massima della sequenza da  ordinare 


int main1();
int main2();
int main3();



/****    MAIN   *****/

int main(){
  return main1();  // esegue main1()
  // return main2();  
  // return main3();  
}



/************    INPUT E OUTPUT       **********/



/* Legge da standard input una sequenza di  al massimo max  interi
   terminante con un carattere non convertibile in intero o con "end-of-file".
   Restituisce il numero di interi letti. */ 

int read(int a[], int max){
  int k;
  for(k=0; k<max && scanf("%d", a+k) == 1 ; k++);
  // il ciclo e'  terminato e k e' il numero di interi letti  
  return k;
}

/* Stampa i primi n elementi dell'array a[]   */

void print(int a[], int n){
  int k;
  for(k=0; k<n; k++)
    printf("%d ", a[k]);
  putchar('\n'); /* a capo */
}



/**************   INSERTION SORT   *********************/

/* Ordina i primi n elementi dell'array a[] usando l'algoritmo  insertion sort */

void insertionSort(int a[], int n){
  // COMPLETARE   
}

int main1(){
 /* COMPLETARE 

Scrivere un main() di prova in cui si legge con read() una sequenza
e la si memorizza in un array v[MAX], si ordina la sequenza  con
 insertionSort()  e la si stampa con print().


Per provarlo, conviene scrivere la sequenza in un file in.txt
e redirigere lo standard input:

a < in.txt


*/ 
  return 0;
}


/******************    QUICKSORT    ***************************************/

/* Scambia *a con *b  */


void swap(int *a, int *b){
  int t=*a;
  *a =*b;
  *b=t;
}

/* Partiziona il sottoarray a[p..r] usando a[r] come perno.
    
   La funzione sistema gli elementi dell'array in modo tale che,  
   posto x=a[r]  e posto q il valore restituito dalla funzione,
   in uscita si ha:
  
   - per i = p,..,q-1, a[i] <= x
   
  -  per j = q+1,..,r,  a[j] >=  x 

  */
 

int partition(int a[], int p, int r){
  // ....
  return 0;
}



/* Ordina il sottoarray  a[p..r]  usando il quicksort. */ 

void quicksort(int a[], int p, int r){
  // ....  
}


/* Ordina i primi n elementi dell'array a[] usando il quicksort  
  (funzione principale da chiamare) */ 

void qksort(int a[], int n){
  // COMPLETARE   
}


int main2(){
/* COMPLETARE 

    main di prova per quicksort()  analogo a main1().

*/  
  return 0;
}




/****************  CONFRONTO  SPERIMENTALE  ********************/



/* Copia i primi n elementi di from[] in to[] */

void copy(int to[], int from[], int n){
  while(n-- >0) // ciclo ripetuto n volte
    *to++ = *from++;   // EQUIVALE A:  *to=*from; to++; from++; 
}





/* Inizializza  un array  a[] con  n interi generati casualmente.
   Si assume che a[] abbia dimensione  >=n   */

void initRandom(int a[], int n){
  // ...  
} 







int main3(){
  clock_t  clock0, clock1;  // per cronometrare  
  double tempo;       // tempo  di esecuzione  
  int dati[MAX], v[MAX];
  
  int n=1;
  
  srand(time(NULL)); // inizializzazione generatore numeri casuali 
 
  printf("Ordina una sequenza n interi generati casualmente\n");

 
  while(n>0){
    printf("\nInserire il valore di n (0 per terminare) --> ");
    scanf("%d", &n);
    if(n <= 0)
      break; // uscita dal ciclo while 
    if(n > MAX){
      printf("Si possono ordinare al massimo %d elementi\n", MAX);
      continue; // si passa a una nuova  iterazione del ciclo while  
    }
    printf("Genera sequenza  random di %d elementi \n\n", n);
    initRandom(dati, n);

    /* Prestazioni  quicksort */
    
    copy(v, dati, n); // copia in v[] gli elementi di dati[] 
    printf("Quicksort (Tempo medio = O(n.log n))::\n");   
    clock0 =  clock(); // tempo iniziale  
    qksort(v, n);
    clock1 =   clock(); // tempo finale 
    tempo = ((double)(clock1 - clock0))/CLOCKS_PER_SEC;
    printf("  %.4f sec.\n", tempo);
 

    /*  Prestazioni  insertion sort */
  
    // ...  COMPLETARE 

  }
 return 0;
}


/* Inizializza a[] in modo con una sequenza di n interi
   che fornisca un caso peggiore per l'algortimo quicksort 
*/

void init(int a[], int n){
  // COMPLETARE e riscrivere main3() inizializzando array dati[] usando init() 
}