=== Imparando.net ===

Quick sort con stringhe

Gli algoritmi di ordinamento sono in grado di ordinare qualunque tipo di dato, non solo interi, a patto che sia definita una relazione d'ordine, cioè scelti due qualsiasi elementi sia possibile dire chi è minore di chi. In questa sezione viene quindi mostrato come primo esempio l'ordinamento di un vettore di stringhe (in C reso come una matrice di char) utilizzando il quicksort. Il codice è sostanzialmente lo stesso, si tratta solo di sostituire le istruzioni per il confronto e lo scambio con quelle corrette per le stringhe (strcmp e strcpy).

Anche se l'algoritmo è lo stesso dovrebbe essere chiaro che il costo per ordinare un vettore di interi è inferiore a quello per ordinare un vettore di stringhe, a causa dei diversi costi delle funzione di confronto e scambio. Se per la funzione di confronto non ci sono modo per velocizzarla, in quanto inerentemente più lenta, si può invece agire sulla parte degli scambi, domandandosi se è davvero necessario spostare "fisicamente" le stringhe o se invece è possibile fare diversamente. La soluzione consiste nell'usare un vettore di supporto i cui elementi puntino, o tramite puntatori o tramite indici, alle stringhe e poi procedere ad ordinare quello, lasciando le stringhe vere nella propria posizione, come si può intuire dalla figura mostrata qua sotto.