Algorisme d'ordenació: diferència entre les revisions

Contingut suprimit Contingut afegit
m Robot: Canvis cosmètics
Línia 1:
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 [[algorisme de recerca|recerca]], [[algorisme merge|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.
 
== Classificació ==
 
Els algorismes d'ordenació es poden classificar de les següents formes:
 
* Pel lloc des d'on es realitza la ordenació:
** [[Ordenació interna|Algorismes d'ordenació interna]]: a la memòria de l'ordinador.
** [[Ordenació externa|Algorismes d'ordenació externa]]: a un lloc extern com pot ser un disc dur.
 
* Pel temps que triguen a realitzar la ordenació:
** [[Algorisme d'ordenació natural|Algorismes d'ordenació natural]]: triga el mínim possible quan l'entrada ja és ordenada.
** [[Algorisme d'ordenació no natural|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.
Línia 19:
Els algorismes es distingeixen per les següents característiques:
 
* [[complexitat computacional]] (pitjor cas, cas mitjà 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ó '''[[Cota superior asintòtica|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]].
Línia 121:
| [[Randomsort]] || ||
|}
 
 
[[Categoria:Algorismes]]