Bogosort: diferència entre les revisions

El '''bogosort ''' també conegut en [[idioma anglès|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. 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). Addicionalment, la seva forma no recursiva ordena les dades-en-el seu-lloc (''in place '', en [[anglès]]), per la qual cosa no es necessita memòria extra per guardar les dades temporals. Stupid sort és un algorisme d'ordenament [[Estabilitat |estable]], la qual cosa significa que dos valors que tinguin el mateix valor es mantindran en el mateix ordre relatiu.

: ''' Mentre ''' ''' no ''' Ordenat (array) ''' fer '''

int i = 0;

while (i <length (array)){

if (array [i+1] <array [i]){

intercanvia (array [i], array [i+1]);

i = 0;

}Else

i++;

}

t_dato aux;//estic usant tipus de dada t_dato per generalitzar la implementació

//Si usessin int o char quedaria limitat a aquesta dada i no es podria utilitzar

//Per un arranjament d'un altre tipus de dada

aux = elem2;

elem2 = elem1;

elem1 = aux;