Bogosort

El bogosort també conegut en anglès com stupid sort, és un algorisme del tipus 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.^[1]

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).

A més a més, 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 estable, la qual cosa significa que dos valors que tinguin el mateix valor es mantindran en el mateix ordre relatiu.

Stupid-sort iteratiu

L'algorisme Stupid-sort iteratiu es pot descriure així:

Inicia pel principi de l'array, l'examina fins a trobar dos elements consecutius fora d'ordre.
Intercanvia aquests dos elements i reinicia l'algorisme (va a la línia 1).
L'algorisme acaba quan arriba al final del vector.

Implementació

En pseudocodi

Mentre no Ordenat (array) fer

Ordenar (array);

En C/C++

bogoSort (array)
{
 int i = 0;

 while (i <length (array)){
 if (array [i+1] <array [i]){
 intercanvia (array [i], array [i+1]);
 i = 0;
 } else {
 i++;
 }
}
void intercanvia (t_dato & elem1, t_dato & elem2)
{
 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;
}

Vegeu també

Bubble-sort

Referències

↑ Mukherjee; India. 1000 Probs In Ds. Tata McGraw-Hill Education, 8 gener 2008, p. 401–. ISBN 978-0-07-066765-5 [Consulta: 29 desembre 2012].

Enllaços externs

Dictionary of Algorithms and Data Structures del NIST (anglès)
Comparativa de diferents algorismes d'ordenació Arxivat 2016-01-13 a Wayback Machine. (anglès)

[MukherjeeIndia2008-1] Mukherjee; India. 1000 Probs In Ds. Tata McGraw-Hill Education, 8 gener 2008, p. 401–. ISBN 978-0-07-066765-5 [Consulta: 29 desembre 2012].

[1]