Quicksort in C

[phoneix86]

Ragazzi nella procedure Partion quando assegno gli indici i e j nn riesco a spiegarmi xkè li assegna fuori al vettore...vi rigrazio anticipatamente




// Quicksort: ordina A[p]...A[r] (p<=f)
void quickSort(int a[], int p, int f , int scelta)
{
int q;
if(p<f) {
q = Partition(a,p,f,scelta);
quickSort(a,p,q,scelta);
quickSort(a,q+1,f,scelta);
}
}







int Partition(int a[], int p, int f,int scelta)
{

int x,scambio;
int i,j;
if (scelta==0) { // se la variabile scelta è 0 allora si avrà il pivot random altrimenti quello fisso al primo elemento
i = (rand()%(f-p)+p); // posizione random
x = a[i]; // pivot
}
else { x=a[p];} // pivot bloccato all'elemento di partenza dell'array

i= p-1; j= f+1; // inizializza indici

for(; {
while(a[--j]>x); // esce se a[j]<=x
while(a[++i]<x); // esce se a[i]>=x

if(i<j) {
// scambia a[i] <-> a[j]
scambio=a[i]; a[i]=a[j]; a[j]=scambio;
}
else break;
}
return j;
}

[YuYevon]

La prossima volta posta il codice utilizzando i tag "code", così non si perde l'indentazione e riusciamo a capirci meglio

Per quanto riguarda la domanda, la risposta è semplice nel momento in cui osservi queste righe:

for ( ; ; ) {
   while ( a[--j] > x); // esce se a[j]<=x
   while ( a[++i] < x ); // esce se a[i]>=x
...

in pratica come vedi j viene predecrementato e i preincrementato. Supponiamo ad esempio che l'array abbia 10 elementi: il minimo valore dell'indice di scorrimento sarà 0 e il massimo 9, quindi avremo i = -1 e j = 10. Quando vengono eseguite quelle istruzioni, j viene decrementato prima di eseguire lo spiazzamento, quindi da 10 passa a 9 e poi viene appunto considerato l'elemento a[9], che esiste perché abbiamo detto che l'array ha 10 elementi. Stessa cosa con il preincremento di i: inizialmente vale -1, viene incrementato e quindi varrà 0 e subito dopo viene calcolato qual è l'elemento dell'array di indice 0, legittimamente.

Se al posto del preincremento e del predecremento avessi avuto un postincremento e un postdecremento, l'algoritmo non avrebbe funzionato...

Probabilmente, comunque, puoi modificarlo così (prova):

i= p; j= f; // inizializza indici

for ( ; ; ) {
   while ( a[j--] > x ); // esce se a[j]<=x
   while ( a[i++] < x ); // esce se a[i]>=x

anche se mi rendo conto che in questo modo, una volta usciti dai due while, i e j non corrisponderanno agli elementi da scambiare ma (rispettivamente) a quello successivo e a quello precedente, questo appunto perché incremento e decremento vengono effettuati dopo. Si può ovviamente ovviare alla cosa così:

for ( ; ; ) {
   while ( a[j--] > x ); // esce se a[j]<=x
   while ( a[i++] < x ); // esce se a[i]>=x

j++;
i--;

if (...

ma perché fare un incremento e un decremento in più ogni volta? Ecco spiegato il motivo di quelle "strane" inizializzazioni :]

[phoneix86]

ti ringrazio x il kiarimento se stato preziosissimo!!!!