Algorisme d'ordenació
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ó
[modifica]Els algorismes d'ordenació es poden classificar de les següents formes:
- Pel lloc des d'on es realitza l'ordenació:
- Algorismes d'ordenació interna: a la memòria de l'ordinador.
- Algorismes d'ordenació externa: a un lloc extern com pot ser un disc dur.
- Pel temps que triguen a realitzar l'ordenació:
- Algorismes d'ordenació natural: triga el mínim possible quan l'entrada ja és ordenada.
- Algorismes d'ordenació no natural: triga el mínim possible quan l'entrada està inversament ordenada.
- 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.
| Estables | ||
| Nom | Complexitat | Memòria addicional |
| Ordenament de bombolla (Bubblesort) | O (n²) | |
| Bombolla bidireccional (Cocktail sort) | O (n²) | |
| Ordenació per inserció (Insertion sort) | O (n²) | |
| Ordenació per caselles (Bucket sort) | O (n) | O(n) |
| Counting sort | O (n+k) | O(n+k) |
| Merge sort | O (n log n) | |
| Arbre binari (Binary tree sort) | O (n log n) | O(n) |
| Pigeonhole sort | O (n+k) | O(k) |
| Radix sort | O (nk) | O(n) |
| Stupid sort | O (n³) versió recursiva | O(n²) |
| Gnome sort | O (n²) | |
| Inestables | ||
| Nom | Complexitat | Memòria addicional |
| Shell sort | O (n1.25) | |
| Comb sort | O (n log n) | |
| Selection sort | O (n²) | |
| Heapsort | O (n log n) | |
| Smoothsort | O (n log n) | |
| Ordenació ràpida (Quicksort) | Mitjana: O (n log n), pijor cas: O(n²) |
|
| Several Unique Sort | Mitjana: O (n u), pijor cas: O(n²); u=n; u = nombre únic de registres |
|
| Qüestionables, inpràctics | ||
| Nom | Complexitat | Memòria addicional |
| Bogosort | O (n × n!), pitjor: no acaba | |
| Pancake sorting | O (n), excepte en màquines de Von Neumann |
|
| Randomsort | ||
Vegeu també
[modifica]Referències
[modifica]- ↑ Mukherjee; India. 1000 Probs In Ds. Tata McGraw-Hill Education, 8 gener 2008, p. 400–. ISBN 978-0-07-066765-5 [Consulta: 29 desembre 2012].
- ↑ Gopal. Magnifying Data Structures. PHI Learning Pvt. Ltd., p. 394–. ISBN 978-81-203-4019-0 [Consulta: 28 desembre 2012].
Enllaços externs
[modifica]
A Wikimedia Commons hi ha contingut multimèdia relatiu a: Algorisme d'ordenació
- Dictionary of Algorithms and Data Structures del NIST (anglès)
- Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)