/*** Sorice - 6 febbraio 2026
Algoritmi di ordinamento
e prova tempi di esecuzione
al crescere dei dati in ingresso,
i vettori vengono riempiti con numeri pseudocasuali***/

/**** fai scegliere all'utente l'ordinamento che desidera */

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


#define MAX 1000000000  /*Massimo 1 mldo elementi*/
int v[MAX];


// Random(X) ritorna un numero fra 1 e X

int Random(int N)
{
    static int primavolta = 1; // BOOLEANO
    if (primavolta)
    {
        srand(time(NULL)); /* inizializzo il seme */
        primavolta = 0;
    }
    return (rand() % N) + 1;
}

void riempi(int v[], int nelem)
{
     int i;
     for(i=0; i <nelem; i++) /*** riempilo con N numeri pseudocasuali fra 1 e N ***/
        v[i]=Random(nelem);
}

void scambia(int v[], int px, int py)
{
    int dep=v[px];
    v[px] = v[py];
    v[py] = dep;
}


void visualizza(int v[], int nelem)
{
    int i;
    int c;
    for(i=0; i < nelem; i++)
    {
        printf("v[%d]=%d\n",i,v[i]);
        if (i%24==0 && i !=0)
        {
            printf("Ancora (S/N)-->");
            c = getchar(); /// pesco il carattere
            getchar(); /// pesco l'invio
            ///printf("c=[%c] - asci[%d]\n",c,c);
            if (c == 'N' || c == 'n')
                return; /// mi fermo
        }

    }
}


void bubblesort(int v[], int dim)
{
    int i;
    int scambio; /// booleano a falso
    do
    {
        scambio=0;/// falso
        for(i=0; i < dim-1; i++)
            if (v[i] > v[i+1])
            {
                scambia(v,i,i+1);
                scambio=1; /// vero
            }

    }
    while(scambio);     /// giro finche scambio e' vero, cioe' ho fatto almeno 1 scambio

}


void bubblesort2 (int v[], int nelem)
{

    int i, j;

    for (i = 0; i < nelem -1; i++)    //ciclo fino al penultimo
        for (j = i+1; j < nelem; j++) //ciclo interno
            if (v[i] > v[j])
                scambia(v,i,j);

    /***Non basta mai un solo ciclo for per ordinare un vettore***/

}

int pminimo (int v[], int x, int nelem)
{

    int pm = x;
    int i;

    for (i = x; i < nelem; i++)
        if (v[i] <v[pm])
            pm = i;

    return pm;
}


void selectsort (int v[], int nelem)
{
    int i, pm;

    for (i = 0; i < nelem -1; i++)            // Trova indice del minimo da i in poi
    {
        pm=pminimo(v,i,nelem);                 // Scambia v[i] con v[pm]
        if (pm != i)
            scambia(v,i,pm);
    }
}

void insertsort(int v[], int nelem)
{
    int temp, i, j;
    for (i = 1; i < nelem; i++)
    {
        temp = v[i];
        j = i -1;
        while(j >= 0 && v[j] > temp)
        {
            v[j +1] = v[j];
            j--;
        }
        v[j +1] = temp;
    }
}


int confronto (int v1[], int v2[])
{
    return (v1[0] - v2[0]);  //Ordine crescente
}


int main()
{
    time_t inizio, fine;
    double tempo_reale;



    int i;
    int nelem; /// numeri elementi del vettore
    ///int v[]={1,4,-4,-2,0,1,7 };
    //system("bubblesort.png"); /// visualizza l'immagine
    do
    {
        char invio; /// solo per invio pendente
        printf("Quanti elementi metto nel vettore ?(max %d) ->",MAX);
        scanf("%d%c",&nelem,&invio);
        /*** chiedi all'utente quanti N elementi vuol mettere nel vettore ***/
    }
    while(nelem < 2 || nelem > MAX);


   riempi(v, nelem);


    printf("Inizio Ordinamento QuickSort...\n");
    inizio = time(NULL);  // Inizio misurazione
    qsort(v, nelem, sizeof(int), confronto);  /*** ordina il vettore***/
    fine = time(NULL);  // Fine misurazione

    tempo_reale = difftime(fine, inizio);
    printf("Fine Ordinamento...\n%c",7);
    printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);


    /*** visualizza il vettore ordinato ***/
    visualizza(v,nelem);


    printf("Inizio Ordinamento BubbleSort...\n");
    riempi(v, nelem);
    inizio = time(NULL);  // Inizio misurazione
    bubblesort(v, nelem);  /*** ordina il vettore***/
    fine = time(NULL);  // Fine misurazione

    tempo_reale = difftime(fine, inizio);
    printf("Fine Ordinamento...\n%c",7);
    printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);


    /*** visualizza il vettore ordinato ***/
    visualizza(v,nelem);
    /*** visualizza il tempo di ordinamento per N elementi ***/
    printf("\n");


    printf("Inizio Ordinamento BubbleSort2...\n");
    riempi(v, nelem);
    inizio = time(NULL);  // Inizio misurazione
    bubblesort2(v, nelem);  /*** ordina il vettore***/
    fine = time(NULL);  // Fine misurazione

    tempo_reale = difftime(fine, inizio);
    printf("Fine Ordinamento...\n%c",7);
    printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);


    /*** visualizza il vettore ordinato ***/
    visualizza(v,nelem);

    printf("Inizio Ordinamento SelectSort...\n");
    riempi(v, nelem);
    inizio = time(NULL);  // Inizio misurazione
    selectsort(v, nelem);  /*** ordina il vettore***/
    fine = time(NULL);  // Fine misurazione

    tempo_reale = difftime(fine, inizio);
    printf("Fine Ordinamento...\n%c",7);
    printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);


    /*** visualizza il vettore ordinato ***/
    visualizza(v,nelem);


    printf("Inizio Ordinamento InsertSort...\n");
    riempi(v, nelem);
    inizio = time(NULL);  // Inizio misurazione
    insertsort(v, nelem);  /*** ordina il vettore***/
    fine = time(NULL);  // Fine misurazione

    tempo_reale = difftime(fine, inizio);
    printf("Fine Ordinamento...\n%c",7);
    printf("Tempo reale trascorso: %.2lf secondi\n", tempo_reale);


    /*** visualizza il vettore ordinato ***/
    visualizza(v,nelem);



    return 0;
}