/***     ALGORITMI PER ORDINARE  ARRAY DI INTERI      ***/ 


#include <stdio.h>



/**** LETTURA E STAMPA DI ARRAY  ****/

/* 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 readArray(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 printArray(int a[], int n){
  int k;
  for(k=0; k<n; k++)
    printf("%d ", a[k]);
  putchar('\n'); /* a capo */
}

/******************    INSERTIONSORT    ***************************************/

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

void insertionSort(int a[], int n){
  int key,i,j;
  for (j=1; j<= n-1; j++){
    /* sistema a[j] in a[0..j-1] */
    key = a[j];
    i = j-1;
    while(i>=0 && a[i] > key){
      a[i+1] = a[i];
      i--;
    }
    a[i+1] =key;
  }
}


/*** MAIN DI PROVA PER INSERTIONSORT ***/

#define MAX 100

int main1(){
    int v[MAX], n;
   n = readArray(v,MAX);
  insertionSort(v, n);
  printArray(v,n);
  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){
  int x,i,j;
  x = a[r];
  i = p-1;
  for(j=p ; j<= r-1; j++){
    if(a[j]<=x){
      i++;
      swap(a+i, a+j);
    }
  }
  swap(a+i+1,a+r); 
  return i+1;
}



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

void quicksort(int a[], int p, int r){
  int q;
  if (p<r){
      q = partition(a, p, r);
      quicksort(a, p, q-1);
      quicksort(a, q+1, r);
    }
}



/*** FUNZIONE PRINCIPALE PER QUICKSORT ***/


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

void qksort(int a[], int n){
  quicksort(a, 0, n-1);
}


/*** MAIN DI PROVA PER QUICKSORT ***/


int main2(){
  int v[MAX], n;
  n = readArray(v,MAX);
  qksort(v, n);
  printArray(v,n);
  return 0;
}