Newsgroup: it.comp.lang.c
Titolo: Quicksort ricorsivo

        Salve,
ho un esercizio che mi chiede di convertire il quicksort (ne riporto la 
versione utilizzata di seguito) da ricorsivo ad iterativo.
        Non riesco a farlo, ringrazio chiunque riesca ad aiutarmi. 
void quicksort(int v[], int n) {
  int i, last;
  if (n <= 1) /* niente da fare */
    return;
  swap(v,0,rand()%n); /* sposta l'elemento di pivot in v[0] */
  last = 0;
  for(i=1; i<n; i++) /* esegue la partizione */
    if(v[i] < v[0])
      swap(v, ++last, i);
  swap(v, 0, last); /* recupera il pivot */
  quicksort(v,last); /* ordina ricorsivamente */
  quicksort(v+last+1, n-last-1); /* ogni parte */
}
void swap (int v[], int i, int j) {
  int temp;
  temp = v[i];
  v[i] = v[j];
  v[j] = temp;
}
ciao a tutti
-- 
Davide Petilli
e-mail. 
davide....@NOSPAM.libero.it
Per scrivermi togli NOSPAM dal mio indirizzo!

ciao a tutti
lo swap come fa a funzionare se tu lavori su altre copie di oggetti ?
prova a fare
swap(int &v[], int i, int j) ...
e quicksort(int &v[], int n)
ciao
cod

 cod


 ha scritto nel messaggio
news:os3fptsgjei1b7l0n...@4ax.com...

Guarda che gli array vengono passati sempre per reference!
Inoltre se tu scrivi swap(int &v[] e quello che č, stai
scrivendo un prototipo, che nel caso č valido solo in C++.
Quando tu chiami scrivi:
int v[10];
v significa &v[0], quindi stai passando l'array per
reference.
--
Paolo Giarrusso


Prima metti apposto il quicksort recursivo, una volta funzioni quella:
cerca di emulare lo stack (come nella funzione recursiva).
crei un struct che contiene i valori passati alla funzione (n) e quelli
locali della funzione (i,last).
Poi definisici un stackpointer (int sp=0;) ed ogni volta in cui dovresti
chiamare
nella versione recursiva la funzione quicksort aumenti nella versione
iterativa lo
stackpointer, setti i valori nella struttura e vai a capo della iterazione.
Ogni volta
che hai finito un pezzo del ordinamento diminuisci lo stackpointer e vai di
nuovo
a capo...
J.

 }
Ti sei imbarcato in un casino (direi anzi che hai proprio
imbracato)!
Ecco la soluzione: se la dimensione di v[] è n, dichiara un
array di dimensione n di int:
int * param1[n]; /*non è ansi C, ma molti compilatori lo
accettano; altrimenti usa :
int * nexts;
nexts = malloc (n*sizeof(int));
*/
Ora, il succo è: definiamo le chiamate di livello n: la
prima chiamata ha livello 1, le chiamate ricorsive che lei
fa hanno livello 2; le chiamate fatte da ogni chiamata
livello 2 sono livello 3, e così via. Ora, ogni iterazione
di while considera le chiamate di un certo livello, mentre
la for "punto 1" contenuta itera tra le varie chiamate
ricorsive dello stesso livello. All'interno della for punto1
devi inserire il codice per ogni chiamata, che prenderà i
suoi parametri da param1[index] e param2[index]:
void quicksort(int v[], int n){
int i, last, index;
int * param1[n];
int param2[n];
int start, end, curr;
start=0;
end=curr=1;
param1[0]=v;
param2[0]=n;
  while (true) {
     for ( index=start; index<end; i++){ //punto 1; itera da
start incluso a end escluso
    swap(param1[index],0,rand()%param2[index]); /*
sostituisco v ed n con param1[index] e param2[index]; si
tratta
di due stack, che agiscono proprio come lo stack che
registra le chiamate delle funzioni */
    last = 0;
/*in queste 4 righe devi sostituire tu v e n come ho detto
poco fa; ho poco tempo*/
   if (n <= 1) /* mettilo tu al suo posto; al posto di
return ci va continue */
     return;
    for(i=1; i<n; i++) /* esegue la partizione */
      if(v[i] < v[0])
/*fine delle 4 righe*/
        swap(param1[index], ++last, i);
     swap(param1[index], 0, last); /* recupera il pivot */
     param1[curr]=param1[index]; // memorizziamo i dati per
le successive chiamate nello spazio del livello successivo
     param2[curr]=last;
     curr++;
     param1[curr]=param1[index]+last+1;
     param2[curr]=n-last-1;
     curr++;
      }  //fine for index
     /*passiamo al livello successivo; l'inizio e la fine di
un livello sono demarcati da start e end, quindi inseriamo i
nuovi valori*/
    start= end; //il primo valore su cui abbiamo scritto;
    end= curr; //abbiamo scritto un valore su param1 e
param2 e poi l'abbiamo incrementato; quindi end è di nuovo
un valore vuoto.
   }//fine while
 }
unica differenza:
quicksort ricorsivo:
chiamata L1, poi chiamate L2a, L3aa ecc; e poi chiamata L2b
quicksort iterativo:
chiamata L1, poi tutte le chiamate L2, poi quelle L3 (cioè
livello 1, livello 2, livello 3)
ma penso non faccia differenza( verifica tu)
Occhio, ho scritto di fretta e ci potrebbe essere qualche
bug, comunque ti ho spiegato l'idea: crea uno stack in cui
leggi i parametri della chiamata corrente in un punto e
scrivi i parametri delle chiamate da eseguire in un altro
punto dello stack; le "chiamate" in realtà sono differenti
iterazioni della for punto 1 (le differenti iterazioni della
while agiscono a differenti livelli; nella while c'è la for
punto1 e il codice che prepara start ed end per il
successivo livello).
Per quanto riguarda le dimensioni di param1 e param2, penso
che dovrebbero bastare le dimensioni dell'array da ordinare.
-Perché il pivot con rand?
-Anziché usare param1 e param2, crea una struct { int*par1;
int par2 } per essere più ordinato.
In ogni caso, poi dimmi dove hai preso questo quicksort: me
lo ricordo molto diverso io.
--
Paolo Giarrusso