codice:
#include<stdio.h>
#include<stdlib.h>
#include<string.h> /* libreria per poter usare le funzioni per la gestione delle stringhe */
#define NUM_STR 8 /* che definisce di quante stringhe è composto il vettore */
#define DIM_STR 20 /* etchetta che definisce la lunghezza massima delle stringhe del vettore */
#define PARTIZIONE 5 /* che definisce la soglia fissata per il cambio di algoritmo di ordinamento */
void inserimento(char array[NUM_STR][DIM_STR]) /*funzione che inserisce nel vettore di stringhe l'imput da tastiera */
/*riceve come parametro solo il l'array e non restituisce nessun parametro */
/*tranne che il vettore tramite indirizzo */
{
int i; /*indice di scorrimento del vettore */
for(i=0;i<NUM_STR;i++) /*ciclo di scorrimento. Parte da 0 e finisce a NUM_STR */
gets(array[i]); /*inserisco nel vettore la stringa in posizione i con l'apposita funzione */
/*che riceve come parametro un 'char *' */
}
void stampa(char array[NUM_STR][DIM_STR]) /*funzione che stampa l'array ordinato. Riceve come parametri in ingresso il */
/*vettore di stringhe. */
{
int s; /*indice di scorrimento del vettore */
for(s=0;s<NUM_STR;s++) /*ciclo di scorrimento. Parte da 0 e finisce a NUM_STR */
puts(array[s]); /*stampo a video la stringa in posizione i con l'apposita funzione */
/*che riceve come parametro un 'const char *' */
}
void inserzione(char array[NUM_STR][DIM_STR],int ileft,int iright) /*Questa funzione contiene l'ordinamento per inserzione. */
/*Come richiesto dal testo, quando le partizioni del quicksort */
/*diventano più piccole della soglia(PARTIZIONE), il quicksort */
/*richiama questa funzione passando gli estremi di ordinamento */
/*e il vettore. */
/*ileft è l'estremo sinistro, mentre iright quello destro. */
{
int i,j; /*indici che servono a scorrere il vettore. */
i=ileft+1; /*poichè il valore di nel for deve partire da 1 e non da 0, */
/*perché bisogna saltare il primo valore, bisogna aumentare di */
/*1 il margine sinistro, in questo caso ileft. */
char x[DIM_STR]; /*una stringa di supporto, che servirà a contenere una stringa */
/*che dovrà essere trasferita in un'altra cella del vettore. */
for(;i<iright;i++) /*ciclo di scorrimento generale del vettore. Finisce quando i */
/*arriva al valore di iright */
{
strcpy(x,array[i]); /*bisogna copiare nella stringa di supporto il contenuto di */
/*array[i] perché verrà modificato nelle successive istruzioni */
/*e non deve andare perso. */
j=i-1; /*la j viene messa a i-1 perché deve controllare tutto il */
/*vettore alla ricerca di una posizione in cui bisogna mettere*/
/*il nuovo elemento.*/
while((j>=0) && (strcmp(x,array[j])<0)) /*1°condizione: una sentinella. non si può andare oltre */
/*l'estremo sinistro della parte di vettore già ordinata. */
/*2°condizione: ricerca del posto in cui mettere il valore */
{
strcpy(array[j+1],array[j]); /*scambio di stringhe. In quesot modo viene trovato lo spazio */
/*posizionare il valore contenuto in x */
j--; /*sentinella decrementata. In questo modo viene aggiornato */
/*il limite dell'estremo sinistro */
}
strcpy(array[j+1],x); /*il valore di x viene messo nella cella del vettore che è */
/*stata liberata. */
}
printf("Ordinamento per inserimento\n");
}
void q_sort(char array[NUM_STR][DIM_STR], int ileft, int iright) /*Questa funzione contiene il corpo dell'ordinamento quicksort */
/*Riceve come parametri gli estremi del vettore, chiamati */
/*ileft e iright. La prima volta che si entra, il primo è a 0, */
/*il secondo a NUM_STR. */
{
int l_hold = ileft; /*questa variabile serve per il ripristino del valore di ileft */
/*così, quando alla fine del programma, ileft dovrà essere */
/*riportata al suo valore iniziale questo non sarà andato */
/*perso */
int r_hold = iright; /*questa variabile serve per il ripristino del valore di */
/*iright così, quando alla fine del programma, iright dovrà */
/*essere riportata al suo valore iniziale questo non sarà */
/*andato perso. */
int aus; /*variabile ausiliaria che conterrà le stringhe da modificare */
char pivot[DIM_STR]; /*questa variabile servirà per contenere il valore della */
/*stringa cardine, quella stringa che servirà da confronto */
/*per tutto il programma */
char t[DIM_STR]; /*variabile ausiliaria che conterrà le stringhe da modificare */
strcpy(pivot,array[ileft]); /*La variabile pivot viene settata con il primo valore del */
/*vettore, almeno la prima volta. Nelle volte successive, */
/*essendo qiesta funzione una funzione ricorsiva, verrà */
/*settata ad un valore diverso ogni volta, un valore */
/*dipendente da ileft. */
while (ileft < iright) /*la condizione controlla che il valore di ileft sia minore */
/*di quello di iright, segno che ci sono ancora valori da */
/*controllare. */
{
while ((strcmp(array[iright],pivot)>=0) && (ileft < iright)) /*in questo while, la variabile iright viene diminuita di */
/*un valore ogni volta che il valore di array[iright] è */
/*maggiore o uguale a quello di pivot e che ileft sia sempre */
/*minore di iright */
iright--; /*diminuzione di iright. */
if (ileft != iright) /*questa condizione viene esaudita quando, nel ciclo */
/*precedente, il loop è terminato non per la seconda */
/*condizione, ma per la prima, segno che i valori sono finiti */
/* e che si è trovato il punto in cui fare lo scambio tra */
/*la variabile puntata da ileft e quella puntata da iright. */
{
strcpy(t,array[ileft]); /*in questo gruppo di istruzioni viene effettuato lo scambio */
strcpy(array[ileft],array[iright]); /*tra le due stringhe, reso possibile dalla presenza della */
strcpy(array[iright], t); /*variabile ausiliaria t; */
ileft++; /*viene aumentata ileft perché adesso il primo valore è stato */
/*controllato e posizionato al posto giusto */
}
while ((strcmp(array[ileft], pivot)<=0) && (ileft < iright)) /*in questo while, la variabile ileft viene aumentata di */
/*un valore ogni volta che il valore di array[ileft] è */
/*mimore o uguale a quello di pivot e che ileft sia sempre */
/*minore di iright */
ileft++; /*aumento di ileft. */
if (ileft != iright) /*questa condizione viene esaudita quando, nel ciclo */
/*precedente, il loop è terminato non per la seconda */
/*condizione, ma per la prima, segno che i valori sono finiti */
/* e che si è trovato il punto in cui fare lo scambio tra */
/*la variabile puntata da iright e quella puntata da ileft. */
{
strcpy(t,array[iright]); /*in questo gruppo di istruzioni viene effettuato lo scambio */
strcpy(array[iright],array[ileft]); /*tra le due stringhe, reso possibile dalla presenza della */
strcpy(array[ileft], t); /*variabile ausiliaria t; */
iright--; /*viene diminuita iright perché adesso il valore è stato */
/*controllato e posizionato al posto giusto */
}
}
strcpy(array[ileft], pivot); /*con questa istruzione sposto i valore che si era deciso di */
/*tenere come pivot al suo posto. Adesso ne verrà scelto un */
/*altro tramite la chiamata ricorsiva. */
strcpy(pivot," "); /*la stringa pivot viene resettata e riempita di spazi. */
aus=ileft; /*viene salvato il valore di ileft */
ileft=l_hold; /*ileft viene resettato al suo valore iniziale, come spiegato */
/*al principio della funzione. */
iright=r_hold; /*iright viene resettato al suo valore iniziale, come spiegato */
/*al principio della funzione. */
if(iright-ileft<PARTIZIONE) /*in questo if viene controllato se la grandezza della */
/*partizione ha raggiunto la soglia. */
inserzione(array,ileft,iright); /*Viene chiamato l'ordinamento di inserzione, come chiesto */
/*dal testo. */
else /*altrimenti */
{
if (ileft < aus) /*viene controllato l'estremo sinistro */
q_sort(array, ileft, aus-1); /*chiamata alla funzione ricorsiva. L'unico parametro che */
/*varia è iright, che assume il valore di aus-1 */
if (iright > aus) /*viene controllato l'estremo destro */
q_sort(array, aus+1, iright); /*chiamata alla funzione ricorsiva. L'unico parametro che */
/*varia è ileft, che assume il valore di aus+1 */
}
printf("Ordinamento Quicksort\n");
}
int main(int argc, char *argv[]) /*inizio del corpo main del programma. I parametri che */
/*riceve sono opzionali e possono essere tolti. */
{
char array[NUM_STR][DIM_STR]; /*viene definito il vettore di stringhe, contenente NUM_STR */
/*stringhe di grandezza DIM_STR. */
inserimento(array); /*si richiama la funzione di inserimento. Come si vede nel */
/*corpo della funzione, riceve un solo parametro ma non */
/*ritorna niente tramite return. */
q_sort(array,0,NUM_STR); /*chiamata alla funzione di ordinamento. Riceve come */
/*parametri il vettore e i due estremi che, nel primo caso, */
/*sono uno a 0, che è l'inizio del vettore, l'altro a NUM_STR, */
/*che è il massimo. */
stampa(array); /*chiamata alla funzione di stampa. Riceve un solo parametro. */
system("pause"); /*chiamata alle funzionalità DOS, che attende la pressione di */
/*un tasto prima di terminare il programma.ù */
return 0; /*poiché si è scelto di definire il main come int, viene */
/*ritornato il valore di default(0) a windows. */
} /*end ordinamento. */
Ci sono alcuni problemi:
Rispondi quotando