--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.

Sorgenti ...

Main.cpp
Main indici.cpp
Main puntatori.cpp

Altro ...

Main.html
Main indici.html
Main puntatori.html
Licenza Creative Commons
Didattica di Alessandro Bugatti è distribuito con Licenza Creative Commons Attribuzione - Non commerciale - Non opere derivate 3.0 Unported.