Newsgroup: it.comp.lang.c
Titolo: AIUTO!!! Su ordinamento quicksort di un vettore

Ciao a tutti, prima di tutto...
Sono uno studente e ho necessità di risolvere il seguente problema:
Ordinamento di un vettore col metodo quicksort da svolgere con una funzione
ricorsiva.
Praticamente se ho un vettore:
1. Prendo il primo elemento e lo confronto coll'ultimo
    1.1 Se è uguale lo scambio
    1.2 Altrimenti lo confronto coll'ultimo-1
2. Dopo il primo scambio confronto il nuovo elemento col primo+1
    2.1 Se uguale lo scambio
    2.2 Altrimenti lo confronto col primo+1
3. I passi 1. e 2. si arrestano quando mi ritrovo a confrontare
l'elemento-perno con se stesso
E questo è il passo ricorsivo. Mi ritroverò con l'elemento perno fissato
nella sua posizione finale e con due sottovettori:uno a destra (non c'è
ovviamente se l'elemento è il maggiore del vettore) e uno a sinistra (che
non c'è ovviamente se l'elemento è il minore del vettore). Con questi dovrò
operare nello stesso modo di prima... e farlo ancora per tutti i
sottovettori che a seconda della lunghezza del vettore si formeranno.
Sono riuscito a creare il passo ricorsivo, quello per cui un elemento si
pone nella sua posizione finale ma non riesco a trovare una regola di
ricorsività che permetta la ripetizione del passo fino a che il vettore sia
totalmente ordinato.
Il programma realizzato finora  è questo:
# include <stdio.h>
# define SIZE 100
void quicksort(int [], int, int);           /* Funzione che dovrebbe gestire
l'ordinamento del vettore */
void partizione(int [], int*, int*);      /* Funzione che effettua il passo
ricorsivo */
main ()
{
int vettore[SIZE], i, assegnatore=100;
for (i=0; i<SIZE; i++)
{
/* Inizializzo il vettore */
 vettore[i]=assegnatore;
 assegnatore--;
 }
printf ("Il vettore prima dell'ordinamento:\n\n");    /* Stampo il vettore
prima dell'ordinamento */
for (i=0; i<SIZE; i++)
  {
  printf ("%3d", vettore[i]);
  if (i>0 && ((i+1)%20)==0)
   printf ("\n");
  }
quicksort(vettore,0,99);                  /* Chiamo la funzione che mi
dovrebbe ordinare il vettore */
printf ("\n\nIl vettore dopo l'ordinamento:\n\n");  /* Stampo il vettore
dopo l'ordinamento */
for (i=0; i<SIZE; i++)
  {
  printf ("%3d", vettore[i]);
  if (i>0 && ((i+1)%20)==0)
   printf ("\n");
  }
return 0;
}
void quicksort (int vet[], int inf, int sup)
{
partizione (vet, &inf,&sup);           /* Funzione che dovrebbe ordinare il
vettore e che invece */
return;                                     /* per adesso si limita a
chiamare una sola volta il passo ricorsivo */
}
/* Funzione che realizza la partizione */
void partizione (int vet[], int *infPtr, int *supPtr)
{
int perno,temp;
while ((*infPtr) != (*supPtr))        /* Mentre non confronto l'elemento con
se stesso... */
    {
if (vet[(*infPtr)]>vet[(*supPtr)])    /* Confronto rispetto agli elementi
alla sua destra */
 {
 perno= vet[(*infPtr)];
 vet[(*infPtr)]=vet[(*supPtr)];
 vet[(*supPtr)]=perno;
 (*infPtr)++;
 temp=(*infPtr);
 (*infPtr)=(*supPtr);
 (*supPtr)=temp;
 }
else
 {
 (*supPtr)--;                                                    /*
Confronto con gli elementi alla sua sinistra */
 partizione (vet, &(*infPtr), &(*supPtr));
 }
    }
}
Ringrazio fin d'ora chiunque voglia rispondermi.

totalmente ordinato.
Il QuickSort e' un algoritmo della classe Divide and Conquer (il
latino non lo conosco :P), che ordina nella fase di partizione (al
contrario di altri che ordinano durante il merge), quindi quando hai
ottenuto un sottoarray di dimensione 1 questo e' ordinato rispetto a
se stesso (banale) E ordinato rispetto agli elementi adiacenti.
Il passo base quindi e' quando lower bound == upper bound.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 Il passo base quindi e' quando lower bound == upper bound.
Ok, in teoria ci sono... insomma a mano mi riesce di ordinare il vettore con
questo algoritmo... è che proprio non riesco a concludere il programma, cioè
non vado oltre l'ordinamento del primo elemento... non riesco cioè, a
impostare ricorsivamente i passi:
1. Partizione
2. Elabora parte destra
3. Elabora parte sinistra
Il programma lo riposto qui perchè l'ho un po' modificato... non è affatto
definitivo - anche perchè con queste modifiche entra in un loop
infinito...devo ancora capire perchè -, l'unica cosa importante è che la
funzione partizione ritorna il valore del perno middle lasciando inalterati
i valori di indice del limite inferiore e indice del limite superiore...
pensavo poi di richiamare la funzione partizione (che mi sono accorto essere
incompleta ) con i valori
lim. inf. , middle
middle, lim, sup.
Non ho concluso per ragioni di rinc****onimento complessivo...
# include <stdio.h>
# define SIZE 100
void quicksort(int [], int*, int*);     /* Gestisce l'ordinamento */
int partizione(int [], int*, int*);      /*Esegue la partizione */
main ()
{
int vettore[SIZE], i, assegnatore=100;
int inf, sup;
for (i=0; i<SIZE; i++)
 {
 vettore[i]=assegnatore;
 assegnatore--;
 }
printf ("Il vettore prima dell'ordinamento:\n\n");
for (i=0; i<SIZE; i++)
  {
  printf ("%3d", vettore[i]);
  if (i>0 && ((i+1)%20)==0)
   printf ("\n");
  }
inf=0;
sup=99;
quicksort(vettore,&inf,&sup);
printf ("\n\nIl vettore dopo l'ordinamento:\n\n");
for (i=0; i<SIZE; i++)
  {
  printf ("%3d", vettore[i]);
  if (i>0 && ((i+1)%20)==0)
   printf ("\n");
  }
return 0;
}
void quicksort (int vet[], int *inf, int *sup)
{
int middle,temp;
middle=partizione (vet, &(*inf),&(*sup));
return;
}
/* Funzione che realizza la partizione... anzi, che dovrebbe realizzare la
partizione */
int partizione (int vet[], int *infPtr, int *supPtr)
{
int perno,temp;
int i,j,k;
i=(*infPtr);
j=(*supPtr);
while ( i < j )
    {
if (vet[i]>vet[j])
 {
 perno= vet[i];
 vet[i]=vet[j];
 vet[j]=perno;
 k=j;
 return k;
 }
else
 {
 j--;
 partizione (vet, &i, &j);
 }
    }
}
Proverò ancora un pò a pensarci su...

 latino non lo conosco :P), 
Neanche io, ma c'e' sempre google :-)
C:\>iao Angelo
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

}
Tra la chiamata a partition e quella di return devi inserire 2 righe:
quicksort (vet, inf, &vet[middle-1]);
quicksort (vet, &vet[middle+1], sup);
Mancano dei controlli per evitare che tu passi i limiti massimi e
minimi dell'array, ma questo guardalo tu :)
Graficamente ...
dato vet in questo modo...
P:   0   1   2   3   4   5   6
   +---+---+---+---+---+---+---+
V: ! 6 ! 4 ! 2 ! 3 ! 1 ! 9 ! 5 !
   +---+---+---+---+---+---+---+
                 ^
                 !
                cd = 3 (il valore, non la posizione)
deve diventare (slto i passaggi, ma mi pare fin qui ci fossi):
P:   0   1   2   3   4   5   6 
   +---+---+---+---+---+---+---+
V: ! 1 ! 2 ! 3 ! 4 ! 6 ! 9 ! 5 !
   +---+---+---+---+---+---+---+
             ^
             !
            ncd
Ora l'elemento in posizione ncd (quindi posizione 2) e' ordinato, devi
ordinare
- ricorsivamente con la prima chiamata l'array da 0 a 1 e 
- con l'altra chiamata da 3 a 6.


 ha scritto nel messaggio
news:3r4ubugp4k0lutvel...@4ax.com...

Grazie, davvero, grazie....

Per ringraziare, puoi anche eliminare il corpo del messaggio a cui
rispondi... mai sentito parlare di quoting?(leggi il manifesto del gruppo
postato di fresco e capirai di che parlo... praticamente, si lasciano solo
le parti importanti del messaggio a cui rispondi, qui ad esempio niente!)
Serve per ridurre il volume del messaggio e aiutare i lettori a non perdere
tempo.
Ciao!
--
Paolo Giarrusso
Per rispondere togliere solo "TOGLIMI" dall'indirizzo, non _spam.