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:

  • 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
  1. 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]. 
  2. Gopal. Magnifying Data Structures. PHI Learning Pvt. Ltd., p. 394–. ISBN 978-81-203-4019-0 [Consulta: 28 desembre 2012]. 

Enllaços externs

modifica