Algorisme d'ordenació: diferència entre les revisions
Contingut suprimit Contingut afegit
m estandarditzant codi |
m Format |
||
Línia 17:
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ó '''[[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 lineal, per tant O(''n'').
* Ús de memòria i altres recursos computacionals. També s'utilitza la notació O(''n'').
Línia 30:
|-----
| Ordenament de bombolla (''[[Bubblesort]]'')
| [[Cota superior asimptòtica|O]] (''n''²)
|
|-----
| Bombolla bidireccional ([[Cocktail sort]])
| [[Cota superior asimptòtica|O]] (''n''²)
|
|-----
| Ordenació per inserció (''[[Insertion sort]]'')
| [[Cota superior asimptòtica|O]] (''n''²)
|
|-----
| Ordenació per caselles (''[[Bucket sort]]'')
| [[Cota superior asimptòtica|O]] (''n'')
| O(''n'')
|-----
| [[Counting sort]]
| [[Cota superior asimptòtica|O]] (''n''+''k'')
| O(''n''+''k'')
|-----
| [[Merge sort]]
| [[Cota superior asimptòtica|O]] (''n'' log ''n'')
|
|-----
| Arbre binari (''[[Binary tree sort]]'')
| [[Cota superior asimptòtica|O]] (''n'' log ''n'')
| O(''n'')
|-----
| [[Pigeonhole sort]]
| [[Cota superior asimptòtica|O]] (''n''+''k'')
| O(''k'')
|-----
| [[Radix sort]]
| [[Cota superior asimptòtica|O]] (''nk'')
| O(''n'')
|-----
| [[Stupid sort]]
| [[Cota superior asimptòtica|O]] (''n''³) versió recursiva
| O(''n''²)
|-----
| [[Gnome sort]]
| [[Cota superior asimptòtica|O]] (''n''²)
|
|-----
Línia 78:
|-----
| [[Shell sort]]
| [[Cota superior asimptòtica|O]] (''n''<sup>{{mida|85%|1.25}}</sup>)
|
|-----
| [[Comb sort]]
| [[Cota superior asimptòtica|O]] (''n'' log ''n'')
|
|-----
| [[Selection sort]]
| [[Cota superior asimptòtica|O]] (''n''²)
|
|-----
| ''[[Heapsort]]''
| [[Cota superior asimptòtica|O]] (''n'' log ''n'')
|
|-----
| [[Smoothsort]]
| [[Cota superior asimptòtica|O]] (''n'' log ''n'')
|
|-----
| Ordenació ràpida (''[[Quicksort]]'')
| Mitjana: [[Cota superior asimptòtica|O]] (''n'' log ''n''),<br />pijor cas: O(''n''²)
|
|-----
| [[Several Unique Sort]]
| Mitjana: [[Cota superior asimptòtica|O]] (''n'' u),<br /> pijor cas: O(''n''²);<br />u=n; u = nombre únic de registres
|
|-----
Línia 110:
|-----
| [[Bogosort]]
| [[Cota superior asimptòtica|O]] (''n'' × ''n''!), pitjor: no acaba
|
|-----
| [[Pancake sorting]]
| [[Cota superior asimptòtica|O]] (''n''), excepte en<br />[[màquina de Von Neumann|màquines de Von Neumann]]
|
|-----
| |||