/******************************************************************************
Quicksort: divide et impera!
*******************************************************************************/
#include <stdio.h>
#include <conio.h>

#include <iostream>
#include <stdlib.h>

#define NRO_ELEMENTI 100
#define TEST_MODE 1

int nc = 0, n_elem;

int
carica_vettore (int a[]){
  int n, i;

    do{
        printf ("Quanti elementi vuoi caricare ? ");
        scanf ("%d", &n);		//cin>>n;
    } while (n <= 0 || n > NRO_ELEMENTI);

    for (i = 0; i < n; i++){
      printf ("elemento %d: ", i);
      scanf ("%d", &a[i]);
    }
  return (n);
}

void stampa_vettore (int a[], int p, int u){
  int i;
    for (i = p; i <= u; i++){
      printf ("%d ", a[i]);
    }
    printf ("\n");
  return;
}


void scambia (int a[], int x, int y){
  int temp;
  temp = a[x];
  a[x] = a[y];
  a[y] = temp;


}

void colora (int a[], int start, int end, int term2_confronto, int perno,int scambio){
  int i;

    for (i = 0; i < start; i++){
        printf ("\033[0m");
        printf ("%d ", a[i]);
    }

    for (i = start; i <= end; i++){
        if (i == term2_confronto && i == perno){
	        printf ("\033[1m\033[36m");	// bold cyan
	    }
        else{
	        if (i == term2_confronto){
                printf ("\033[1;32m");	//green
	        }else{
                if (i == perno){
	                printf ("\033[1;31m");	//red
	       		}
	            else{
	                printf ("\033[1;33m");	//yellow
	            }
	        }
	    }
        printf ("%d ", a[i]);
    }

    for (i = end + 1; i < n_elem; i++){
        printf ("\033[0m");
        printf ("%d ", a[i]);
    }

    if (scambio == 1) printf ("\033[0m <<");
    printf("\n");
}


int partiziona (int a[], int sx, int dx) {
    int p, dx1, sx1, i;
    dx1 = dx;
    sx1 = sx;
    
    while (sx < dx){
        p = sx;
        while (a[dx] >= a[p] && dx > p){
            nc++;
            dx--;
            colora (a, sx1, dx1, dx, p, 0);
        }
    

        //colora (a, sx1, dx1, dx, p, 1);
        scambia (a, p, dx);
    
        p = dx;
        while (a[sx] <= a[p] && sx < p){
            nc++;
            sx++;
            colora (a, sx1, dx1, sx, p, 0);
        }
    

        //colora (a, sx1, dx1, sx, p, 1);
        scambia (a, p, sx);
    }
    
    return p;
}

void quicksort (int a[], int primo, int ultimo){
  int q;
/*pivot -- inizialmente il pivot C( il primo elemento
primo e ultimo sono le due variabili che servono per 
scorrere l'array
*/

    if (primo < ultimo){
        q = partiziona (a, primo, ultimo);
        quicksort (a, primo, q - 1);
        quicksort (a, q + 1, ultimo);
    }
}


int main () {

#if (TEST_MODE)
  int a[] = {30,22,15,18,37,19,42,14,21,33,45,65,89,62,51 };
  n_elem = 15;
#else
  int a[NRO_ELEMENTI];
  n_elem = carica_vettore (a);
#endif

  printf ("Vettore iniziale: \n");
  stampa_vettore (a, 0, n_elem - 1);
  printf ("\n");

  colora (a, 0, n_elem - 1, n_elem - 1, 0, 0);

  quicksort (a, 0, n_elem - 1);
  printf ("\nVettore ordinato con quick-sort: \n");
  stampa_vettore (a, 0, n_elem - 1);
  printf ("\nnumero di confronti effettuati: %d", nc);
  return 0;
}