[C]-Problema Quick sort

[-Yara-]

Salve a tutti....
Chi mi aiuta con questo pezzo di codice che non riesco a far funzionare?
Si tratta del quick sort...e si blocca in esecuzione

void Quick(int v[],int sx,int dx)
{
     int pivot=v[(sx+dx)/2];
     int isx=sx;
     int idx=dx;
     while(sx<=dx) {
                   while(v[isx]<pivot) isx++;
                   while(v[idx]>pivot) idx--;
                   if(isx<=idx) {
                                Scambia(v[isx],v[idx]);
                                isx++;
                                idx--;
                                }
                   }
     if(sx<idx) Quick(v,sx,idx);
     if(isx<dx) Quick(v,isx,dx);
return;
}

Inoltre, come potrei modificarlo per far ordinare un vettore in modo decrescente?
Grazie in anticipo

[-Yara-]

up..

[ghiotto86]

puoi mettere anche la funzione scambia??

[Ziosilvio]

Originariamente inviato da -Yara-

while(sx<=dx)

Casomai, "while (isx<=idx)".

[ghiotto86]

Originariamente inviato da Ziosilvio

Casomai, "while (isx<=idx)".

ecco hai ragione.

yara mannaggia a te e chi te fa programmà

[-Yara-]

Originariamente inviato da ghiotto86

ecco hai ragione.

yara mannaggia a te e chi te fa programmà

è colpa del mio Proff che fa casino
Oggi m'ha fatto fare la Torre di Hanoi...che due palle....vabbè torno a studiarmi actionscript va'..senno' cado in depressione
Grazie dell'aiuto

[ghiotto86]

mai fidarsi dei prof.

[Ziosilvio]

Adesso che ci penso...

Originariamente inviato da -Yara-

[code]Scambia(v[isx],v[idx])

Casomai, "Scambia(v+isx,v+idx)", o "Scambia(v,isx,idx)", o al limite "Scambia(&v[isx],&v[idx])"...

[3nigma666]

Uhmm secondo me il tuo algoritmo non è tanto efficiente,non rispetta la complessita di =(nlong) me è superiore.non ti conviene fare cosi:

//--------------------------------------------------------------------------------
// Name  :  swap(long& a, long& b)
// Desc  :  Questa funzione implementa lo scambio dei valori con 
//          la tecnica inplace, ovverosia senza alcuna variabile di supporto
//          Si noti che i parametri sono passati per riferimento, altrimenti 
//          le modifiche sarebbero effettuate su copie di essi, e lo scambio di valore non ci sarebbe.
//          ^= è il simbolo di Xor. Eseguo un Xor per scambiare i valori
// ToDo  :  Nulla  :D
// Vers  :  1.0
//----------------------------------------------------------------------------------------

void swap (long& a, long& b) {
	a ^= b ^= a ^= b; //Metodo inplace per scambiare i valori di a e b
};

////////////////////////////////////////////////////////////////////////////////
//                              QUICKSORT
////////////////////////////////////////////////////////////////////////////////

//-----------------------------------------------------------------------
// Name  :  Partition 
// Desc  :  Prende come parametri puntatore ad un vettore, indice sinistro ,indice destro
//          Inizia a scorrerre il vettore partendo da fuori il vettore
//          e inizia un loop ke continua fino a quando l'indice sx è minore dell'indice dx
//          Dentro al loop viene fatto scorrere il vettore e ogni singolo elemento del vettore
//          viene confrontato con il pivot e se maggiore viene messo a dx se inferiore viene
//          posizionato a sx tramite la funzione swap
// ToDo :   Nulla
// Vers :   1.0
// Bugs :   N.P.
//-----------------------------------------------------------------------------------------

int Partition (long* vett,int left,int right){
     pivot = vett[left];//a pivot assegno il primo elemento
     i = left - 1 ;    //inizio da fuori il vettore
     j = right + 1;   //inizio da fuori il vettore
    //fino a quando l indice inferiore non supera l indice superiore continua a cercare gli elementi 
    while (i < j){
		do{j--;} //decrementa di una posizione l'indice superiore
		while (vett[j]>pivot); //continua a decrementare fino a quando l elemento trovato nn è maggiore del pivot
		do{
            i++;
        }while (vett[i]<pivot);//continua a decrementare fino a quando l elemento trovato nn è minore del pivot
		if (i<j)
			swap(vett[i],vett[j]);//inverti i due valori
        else                  
           return j;// se i ha superato j ritorno il nuovo pivot a Qsort
     }//end while
}//end partition                                 

//-------------------------------------------------------------
// Name  :  QuickSort
// Desc  :  Assegna un valore a al pivot q.la funzione richiama se stessa
//          ricorsivamente passandosi prima l'albero di dx e poi quello di sx
// ToDO  :  Nulla :D
// Vers  :  1.0
// Bugs  :  N.P
//-----------------------------------------------------------

void QuickSort (long* vett,int left,int right){
     if (left < right){
              q = Partition (vett,left,right); //Assegnazione pivot
              QuickSort(vett,left,q);//albero di sinistra
              QuickSort(vett,q+1,right);//albero di destra
              }//end if

}//end quicksort

cosi è perfetto come complessità,anke perke a mio parere non è ottimale come soluzione prendere il pivot come centro del vettore (non ke cambi molto in termini di prestazioni) però..

[Ziosilvio]

Originariamente inviato da 3nigma666

Uhmm secondo me il tuo algoritmo non è tanto efficiente,non rispetta la complessita di =(nlong) me è superiore

La complessita' asintotica dell'implementazione del Quicksort proposta da -Yara- e' O(n log n) nel caso medio e O(n^2) nel caso peggiore.
La complessita' asintotica dell'implementazione del Quicksort proposta da te e' O(n log n) nel caso medio e O(n^2) nel caso peggiore.

swap(long& a, long& b)

Questo e' codice C++. Qui invece si chiede aiuto su un programma C.

a ^= b ^= a ^= b; //Metodo inplace per scambiare i valori di a e b

Questo trucco funziona solo con variabili di tipo intero.

[3nigma666]

per quanto riguarda la complessita del codice hai ragione, è O(nlong) in entrambi i casi ,il suo codice è correttamente scritto.
Per quanto riguarda lo swap mi tocca mentire,ho personalmente presentato un progetto con quella funzione swap cosi come l'ho definita nel mio post applicata a numeri sia float,sia double, senza avere problemi.

[Ziosilvio]

Originariamente inviato da 3nigma666

ho personalmente presentato un progetto con quella funzione swap cosi come l'ho definita nel mio post applicata a numeri sia float,sia double, senza avere problemi.

Se non ci sono stati problemi, allora il tuo compilatore te l'ha permesso: buono a sapersi, perché comunque è una cosa comoda.
L'Appendice A del K&R dice però esplicitamente che gli operatori bit-a-bit sono definiti solo su variabili di tipo intero, quindi quella che hai usato non è una caratteristica del linguaggio. Sarebbe interessante vedere se le cose sono cambiate in C99, di cui però so poco o nulla...

[VICIUS]

Originariamente inviato da 3nigma666

void swap (long& a, long& b) {
a ^= b ^= a ^= b; //Metodo inplace per scambiare i valori di a e b
};

Alla fine apposggiarsi su un registro è molto piu veloce (circa 3x). Questo era un truchetto che era utile quando si aveva poca memoria.

ciao