- Stupid sort
-
Stupid sort, en inglés también conocido como BogoSort, es probablemente el más sencillo de los algoritmos de ordenamiento.
Es utilizado para reorganizar valores en un array (también llamado vector, o arreglo) en orden ascendente o descendente. Su nombre se refiere al hecho de que su extrema sencillez repercute en su baja eficiencia, es decir, su rendimiento es pobre en términos de tiempo de ejecución. Su eficiencia media es O(n*n!), extremadamente ineficiente.
Stupid-sort nunca reitera en ordenar los datos en el mejor caso (es decir, cuando los datos ya estén en orden) con un tiempo de ejecución lineal (en este caso óptimo su tiempo de ejecución es O(n), donde n es el número de elementos en el array). Adicionalmente, su forma no recursiva ordena los datos-en-su-lugar (in place, en inglés), por lo cual no se necesita memoria extra para guardar los datos temporales.
A diferencia del ordenamiento de burbuja, bubble sort, este algoritmo de ordenamiento comienza todo otra vez —esto es, reitera— si encuentra tan solo un elemento fuera de orden. Esto, que simplifica el flujo del algoritmo, conduce a la vez a un tiempo de ejecución muy elevado.
Stupid sort es un algoritmo de ordenamiento estable, lo cual significa que dos valores que tengan el mismo valor se mantendrán en el mismo orden relativo.
Contenido
Stupid-sort iterativo
El algoritmo Stupid-sort iterativo se puede describir así:
- Inicia por el principio del array, lo examina hasta encontrar dos elementos consecutivos fuera de orden.
- Intercambia esos dos elementos y reinicia el algoritmo (va a la línea 1).
- El algoritmo termina cuando llega al final del vector.
Implementación
En pseudocódigo
- Mientras no Ordenado(array) hacer
- Ordenar(array);
En C/C++
bogoSort(array) { int i=0; while (i < length(array)) { if (array[i+1] < array[i]) { intercambia(array[i], array[i+1]); i = 0; } else i++; } } void intercambia(t_dato &elem1, t_dato &elem2) { t_dato aux; // estoy usando tipo de dato t_dato para generalizar la implementación // si usaran int o char quedaría limitado a ese dato y no se podría utilizar // para un arreglo de otro tipo de dato aux = elem2; elem2 = elem1; elem1 = aux; }
Categoría:- Algoritmos de ordenamiento
Wikimedia foundation. 2010.
