Qui il Titolo

Il maledettissimo quicksort

Sapevo che il corso di algoritmi non sarebbe stata una passeggiata ma non credevo di riuscirmi a fottere il cervello fino a questo punto!

Ho iniziato un capitolo del Cormen dove si parla di quicksort e devo dire che all'inizio scorreva tutto liscio come l'olio... studio della complessità, caso peggiore, caso medio etc... alla fine sono quattro conti precisi!

Però mi sono chiesto:
ma saprei implementare quicksort in C?
Mi sono risposto:
credo di si... dai tanto è semplice.

Inizio a scrivere, do ogni tanto un'occhiata allo pseudocodice del libro per controllare che stia seguendo la strada giusta, e finisco con l'implementare una procedura "partition" spiccicata a quella di Cormen... non funziona nulla!
Mi dispero 3 giorni, faccio controlli assurdi sugli indici, riempio un foglio di <= oppure di >=, ma niente non si risolve!
A questo punto ho cominciato a pensare di essere stupido! Non capivo assolutamente quale potesse essere il problema...

Il giorno 3 mi sono deciso a scrivere una partition di testa mia... il quicksort ha funzionato dopo 10 minuti!

Morale della favola: non seguire lo pseudocodice altrui. Se vuoi implementare bene un algoritmo prima lo devi capire!

Saluti
Dario