domanda su quicksort :)

[.:AbboZ:.]

Ciao a tutti,
questo è un misto tra codice e pseudo codice...

static void qs(int[] a, int inf, int sup) {
if(lunghezza di a[inf..sup] <= 3)
isort(a, inf, sup); // cioè ordina a[inf..sup] con un algoritmo elementare
else {
int pivot = a[inf];
int i = inf; int j = sup;
do {
if(a[i] < pivot) i++;
else if(a[j] > pivot) j--;
else {
scambia a[i] con a[j];
i++; j--;
}
} while(i <= j);
qs(a, inf, j);
qs(a, i, sup);
}
}

Se nell'algoritmo precedente si sostituiscono i confronti a[i]<pivot e a[j]>pivot
rispettivamente con a[i]<= pivot e a[j]>= pivot l'algoritmo non è più corretto. Mi sapreste dire il perchè ?? io proprio nn capisco il motivo...

Vi ringrazio in anticipo per l'aiuto.

Ciao ciao

[.:AbboZ:.]

sup ?

nessuno mi saprebbe aiutare ? :(

[gugoXX]

E' gia' almeno la terza volta che vediamo questo codice, pari pari.
Al che viene il dubbio che sia un testo di un problema ufficiale.
Le cui soluzioni sono vietate.

Se io volessi la soluzione e non ci fosse nessuno a cui chiederla, proverei a compilarlo e a debuggarlo con un array da ordinare di prova, e cercherei quindi di capire perche' in un caso funziona e in un altro no.

[.:AbboZ:.]

..ah no no..nn è il mio caso ! Questa è solo una domanda di approfondimento che è presente sulle slide del mio prof..nn c'entra nessun problema ufficiale.
Ero solo curioso di sapere il perchè aggiungendo un semplice "=" il tutto poteva non funzionare...visto che sulle slide non è spiegato e io non ho capito il perchè.

Quindi, nel caso qualcuno sapesse il motivo e sarebbe così gentile da spiegarmelo gliene sarei grato.

Grazie ancora.

Ciao ciao

P.S. ...se vuoi ti passo le slide.. :)

[Guts]

posto che ho guardato due minuti fa cosa fosse il quicksort quindi potrebbe essermi sfuggito qualcosa, ma non è semplicemente che non funziona con gli uguali perchè supereresti il pivot nella tua scansione in quel caso? cioè tu scansioni da sinistra per trovare elementi più grandi e da destra per trovarne di più piccoli rispetto al pivot, quando li trovi li scambi. se però con la i finisci a destra del pivot o con la j finisci a sinistra, finiresti per scambiare elementi che invece sono già a posto.
ciao