[C++] QuickSort

[pippofrank]

Salve dovrei realizzare quicksort (senza utilizzare la qsort di c++).
La situazione è questa: ho un vettore di interi da ordinare che passo alla funzione quicksort. La funzione dovrebbe ordinarmi il vettore che gli passo, ma in realtà ne crea una copia...spero di essermi spiegato..
Ho provato con i puntatori, ma forse sbaglio qualcosa..

Riporto qui il codice:

void Test::QuickSort(int A[],int ind[] ,int p,int r)
{
int q;
if (p < r)
{
q = partition(A, ind, p, r);
QuickSort(A, ind, p, q);
QuickSort(A, ind, q + 1, r);

}


}

int Test::partition(int A[], int ind[], int p, int r)
{
int i, j, temp;
int x;
x = A[ind[p]];
i = p - 1;
j = r + 1;
while (true)
{
do j = j - 1;
while (A[ind[j]] > x); do i = i + 1;
while (A[ind[i]] < x); if (i < j)
{
temp = ind[i];
ind[i] = ind[j];
ind[j] = temp;
}
else return (j);
}
}




dentro il main richiamo la funzione in questo modo:

int ind[MAXNODI];
int distanzaEuclidea[MAXNODI];
QuickSort(distanzaEuclidea, ind, 0, numnodi - 1);


Vorrei quindi che QuickSort mi restituisse lo stesso vettore "distanzaEuclidea" ordinato..
Graizie
Ciao

[cionci]

Riguardati come funziona il while ;)

[pippofrank]

Ho ricontrollato il while. Veramente mi pare che funzioni, anche perchè quello che sto facendo è un porting da c# e c++, e l'algoritmo è esattamente lo stesso...

[cionci]

while (A[ind[j]] > x); do i = i + 1;
while (A[ind[i]] < x); if (i < j)

Questi due cicli non tornano, non ci vuole il ; e non serve il do.

[pippofrank]

do {j = j - 1;}
while (A[ind[j]] > x);
do {i = i + 1;}
while (A[ind[i]] < x);

if (i < j)
{
temp = ind[i];
ind[i] = ind[j];
ind[j] = temp;
}
else return (j);


ma veramente non mi pare..
forse perchè avevo indentato male, ora ho messo le {}...ma non cè nessun do in più.
Comunque a parte questo, la mia questione originale è un'altra: se io passo alla funzione un vettore poi nella funzione quicksort, mi viene ordinato "quel" vettore (nel mio caso distanzaEuclidea) oppure una sua replica A[]??

[cionci]

Mi aveva tratto in inganno l'indentazione :D

Comunque viene ordinato il vettore originale, perché i vettori vengono passati per puntatore.

[Furla]

ma ind[] a che ti serve?

[cionci]

ma ind[] a che ti serve?
Sta scambiando gli indici invece dei dati, a prima vista.

[Furla]

ma ind[] a che ti serve?

EDIT: mi sa che ho capito, ordinando ind, tu ordini gli indici, lasciando invariato l'array originale. per funzionare, ind dovrebbe contenere, inizialmente, tutti i naturali da 0 a MAXNODI in ordine crescente; considera che successivamente, per accedere in modo ordinato all'array, dovrai sempre passare per ind, e non è molto comodo.