Algorisme d'ordenació
De Viquipèdia
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 ex., 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.
[edita] Classificació
Els algorismes d'ordenació es poden classificar de les següents formes:
- Pel lloc des d'on es realitza la 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 la ordenació:
- Algorismes d'ordenació natural: triga el mínim possible quan l'entrada ja és ordenada.
- Algorismes d'ordenación 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 majuscules 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 artificalment 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 promig i millor cas) en termes d'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 quadratics, é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 linial, 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 adicional |
| 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ón recursiva | O(n²) |
| Gnome sort | O(n²) | |
| Inestables | ||
| Nom | Complexitat | Memòria adicional |
| 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) | Promig: O(n log n), pijor cas: O(n²) |
|
| Several Unique Sort | Promig: O(n u), pijor cas: O(n²); u=n; u = nombre únic de registres |
|
| Qüestionables, inpràctics | ||
| Nom | Complexitat | Memòria adicional |
| Bogosort | O(n × n!), pitjor: no acaba | |
| Pancake sorting | O(n), excepte en màquines de Von Neumann |
|
| Randomsort | ||
