Radix sort P69217

Radix sort és un algorisme d’ordenació que usa el fet que els elements dins d’un ordinador estan habitualment compostos per bits, o dígits en general, o caràcters. Aquí, suposarem que ens cal ordenar una seqüència de paraules formades només amb lletres minúscules, totes de la mateixa longitud.

Per implementar radix sort (en una de les variants), ens cal una cua per a cada caràcter possible, i una altra cua Q. Comencem amb totes les paraules dins de Q. Traiem les paraules de Q i les guardem a la cua que toqui en funció del darrer caràcter. Després, les paraules es treuen de la cua de la ‘a’, de la cua de la ‘b’, …, de la cua de la ‘z’, en aquest ordre, i es tornen a deixar a Q. Ara tornem a fer el mateix però en funció del penúltim caràcter. El procés s’itera fins a fer servir el primer caràcter de tots. Al final, Q conté totes les paraules en ordre.

Per exemple, suposem que les paraules són

soc sal mur sac res mar sol sal

Després d’ordenar-les respecte del tercer caràcter, tenim

soc sac sal sol sal mur mar res

Ara ordenem respecte del segon caràcter, i obtenim

sac sal sal mar res soc sol mur

Fixeu-vos que, si esborréssim el primer caràcter de cada paraula, les paraules ja estarien en ordre. Finalment, ordenem respecte del primer caràcter:

mar mur res sac sal sal soc sol

Entrada

L’entrada consisteix en una seqüència de paraules de la mateixa longitud amb només lletres minúscules.

Sortida

Escriviu una línia amb les paraules ordenades de petit a gran.

Observació

Si ordenéssiu les paraules donades amb qualsevol altre mètode eficient, també obtindríeu el resultat demanat i el Jutge no ho detectaria. Però això no us serviria per practicar l’ús de cues, que és del que es tracta.