Bogosort: diferència entre les revisions
Contingut suprimit Contingut afegit
m jerarquia d'encapçalaments |
Robot estandarditza i catalanitza referències, catalanitza dates i fa altres canvis menors |
||
Línia 1:
El '''bogosort''' també conegut en [[anglès]] com '''stupid sort''', és un algorisme del tipus [[Algorisme de Las Vegas|Las Vegas]], i probablement el més senzill dels [[algorismes d'ordenació]]. A diferència del [[bubble-sort]], aquest [[algorisme d'ordenació]] ho comença tot una altra vegada, és a dir, -torna a començar- si troba només un element fora d'ordre. Aquest fet, que simplifica el flux de l'algorisme, condueix alhora a un temps d'execució molt elevat. És utilitzat per reorganitzar valors en un [[array]] (també anomenat vector, o matriu) en ordre ascendent o descendent.<ref name="MukherjeeIndia2008">{{ref-llibre|autor=Mukherjee|coautors=India|títol=1000 Probs In Ds|url=http://books.google.es/books?id=t_if-ZGBcioC&pg=PA401&dq=bogo-sort&hl=ca#v=onepage&q=bogo-sort&f=false|consulta=29
El seu nom es refereix al fet que la seva extrema senzillesa repercuteix en la seva baixa eficiència, és a dir, el seu rendiment és pobre en termes de temps d'execució. La seva eficiència mitjana és O (n * n !), extremadament ineficient. Stupid-sort mai torna a ordenar les dades en el millor cas (és a dir, quan les dades ja estiguin en ordre) amb un temps d'execució lineal (en aquest cas òptim el seu temps d'execució és O (n), on n és el nombre d'elements en l'array).
| |||