En informàtica i matemàtiques un algorisme d'ordenació és un algorisme que posa elements d'una llista seguint l'ordre donat per una relació d'ordre. Les relacions d'ordre més usades són l'ordre numèric i l'ordre lexicogràfic. Ordenar eficientment és important per a posteriorment usar en forma d'altres algorismes com els de recerca, merge, (per exemple, per a la comparació de llistes), atès que per a aplicar certs algorismes és necessari que prèviament els elements es trobin ordenats. També és útil per a posar dades en forma canònica i per a generar resultats llegibles per a humans.[1][2]
Classificació
Els algorismes d'ordenació es poden classificar de les següents formes:
- Pel lloc des d'on es realitza l'ordenació:
- Pel temps que triguen a realitzar l'ordenació:
- Per estabilitat: un ordenament estable manté l'ordre relatiu que tenien originalment els elements amb claus iguals. Per exemple, si una llista ordenada per data la reordenem per ordre alfabètic amb un algorisme estable, tots els elements la clau alfabètica dels quals sigui la mateixa quedaran ordenats per data. Un altre cas seria quan no interessen les majúscules i minúscules, però es vol que si una clau aBC era abans que AbC, en el resultat ambdues claus apareguin plegades i en l'ordre original: aBC, AbC.
- Quan els elements són indistingibles (perquè cada element s'ordena per la clau completa) l'estabilitat no interessa. Els algorismes d'ordenació que no són estables es poden implementar per tal que ho siguin. Un sistema per fer-ho es modificant artificialment la clau d'ordenació i així la posició original en la llista participi de l'ordenament en cas de coincidència.
Els algorismes es distingeixen per les següents característiques:
- complexitat computacional (pitjor cas, cas mitjà i millor cas) en termes de n, la mida de la llista o arrenjament. Per això s'usa el concepte d'ordre d'una funció i la notació O(n). El millor comportament per ordenar (si no s'aprofita l'estructura de claus) és O(n log n). Els algorismes més simples són quadràtics, és a dir, O(n²). Els algorismes que aprofiten l'estructura de les claus d'ordenació (Ex. bucket sort) poden ordenar en O(n k), on k és la mida de l'espai de claus. Com que la mida ja es coneix amb anteriotat, es pot dir que aquests algorismes tenen un sentit lineal, per tant O(n).
- Ús de memòria i altres recursos computacionals. També s'utilitza la notació O(n).
Alguns algorismes d'ordenació agrupats segons l'estabilitat tenint en compte la complexitat computacional.
Vegeu també
Referències
Enllaços externs
