Codice dei programmi nella directory:
///File: ordina.c
/// prova a scrivere un programma C che ordina un vettore
/// riempito con numeri psudocasuali
/// Algoritmo: scambia i valori del vettore, partendo dal primo
/// e arrivando al penultimo, confrontando un elemento con il successivo.
/// se l'elemento e' maggiore del successivo, li scambio.
/// mi fermo quando, avendo passato tutto il vettore, non ho fatto
/// neanche uno scambio.
/// quali funzioni recupero ???
/// Random()
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#define MAX 500000
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 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
}
int main()
{
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);
}
while(nelem < 2 || nelem > MAX);
/*** chiedi all'utente quanti N elementi vuol mettere nel vettore ***/
for(i=0; i <nelem; i++) /*** riempilo con N numeri pseudocasuali fra 1 e N ***/
v[i]=Random(nelem);
/*** ordina il vettore***/
printf("Inizio Ordinamento con bubblesort...\n");
bubblesort(v,nelem);
printf("Fine Ordinamento con bubblesort...\n%c",7);
/*** visualizza il vettore ordinato ***/
visualizza(v,nelem);
/*** visualizza il tempo di ordinamento per N elementi ***/
return 0;
}
///(Fine file: ordina.c)
///File: Bubbesort2.txt
/****
1) trovare un numero di elementi del vettore per cui
la bubblesort() ci mette circa 10 secondi
(circa ...... elementi)
2) codificare e controllare che funziona bubblesort2()
3) lanciare bubblesort2() con il numero di elementi
nel vettore trovato al punto 1) e verificare se il
tempo e' minore o maggiore di 10 secondi
****/
/*** prova di Sorice: 100 mila elementi
bubblesort() ----> circa 50 secondi
bubblesort2()----> circa 30 secondi == piu' veloce di circa 40%
selectsort() ----> dovrebbe essere piu' veloce, limitando gli scambi a N-1
circa fra 12 e 15 secondi per 100 mila elementi
occorre una funzione richiamata N-1 volte, se N e' il numero di elementi
che ritorni la posizione dell'elemento minimo fra x e N con x
crescente (x==0 al primo giro, x == 1 secondo giro, ... x == N-2 ultimo giro
eccola: (vedi sotto pminimo() )
insertsort() ----> occorre una funzione che, detta x la posizione
in cui inserire un elemento, faccia il buco nel vettore
in posizione x spostando gli y elementi a destra..
e' un po' difficile da scrivere...
void insertsort(int a[], int nelem)
{
int temp,i,j;
for (i = 1; i < nelem; i++)
{
temp = a[i];
j = i - 1;
while (j >= 0 && a[j] > temp)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
void selectsort(int v[], int nelem)
{
int i,pm;
for(i=0; i < nelem-1; i++)
{
pm=pminimo(v,i,nelem);
scambia(v,i,pm);
}
}
int pminimo(int v[], int x, int nelem)
{
int pm=x; /// parto da v[x] e cerco il minimo
int i;
for (i=x; i < nelem; i++)
if (v[i] < v[pm])
pm=i;
return pm;
}
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); ///scambia i due elementi del vettore
/// NON BASTA MAI UN UNICO CICLO per ordinare un vettore
}
///(Fine file: Bubbesort2.txt)
///File: qsort.c
#include <stdio.h>
#include <stdlib.h>
int confronto(int v1[], int v2[])
{
return (v1[0]-v2[0]); // Ordine crescente
}
int main() {
int v[] = {5, 2, 9, 1, 5, 6};
int nelem=6;
int i;
qsort(v, nelem, sizeof(int), confronto);
for(i=0; i < nelem; i++)
printf("%d\n",v[i]);
return 0;
}
///(Fine file: qsort.c)
///File: Ordina.c
/*** 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;
}
///(Fine file: Ordina.c)