algorithm - ordenamiento - ¿Hay algún algoritmo de clasificación peor que Bogosort(también conocido como Monkey Sort)?

sorting algorithms

Question

Mis compañeros de trabajo me llevaron al pasado a mis días universitarios con una discusión de algoritmos de clasificación esta mañana. Recordamos nuestros favoritos como StupidSort , y uno de nosotros estaba seguro de que habíamos visto un algoritmo de ordenamiento que era O(n!) . Eso me hizo comenzar a buscar los "peores" algoritmos de clasificación que pude encontrar.

Postulamos que un tipo completamente aleatorio sería bastante malo (es decir, aleatorizar los elementos - ¿está en orden? ¿No? Aleatorizar de nuevo), y miré a mi alrededor y descubrí que aparentemente se llamaba BogoSort, o Monkey Sort, o algunas veces simplemente Random Sort .

Parece que Monkey Sort tiene un rendimiento en el peor de los casos de O(∞) , un mejor rendimiento de O(n) , y un rendimiento promedio de O(n·n!) .

¿Hay algún algoritmo con nombre que tenga un rendimiento promedio peor que O(n·n!) ? ¿O son más tontos que Monkey Sort en general?

Answer 1

El "¿qué te gustaría que fuera?" ordenar

1. Tenga en cuenta la hora del sistema.
2. Ordenar utilizando Quicksort (o cualquier otra cosa razonablemente sensible), omitiendo el último intercambio.
3. Tenga en cuenta la hora del sistema.
4. Calcule el tiempo requerido. La aritmética de precisión extendida es un requisito.
5. Espere el tiempo requerido.
6. Realice el último intercambio.

No solo puede implementar ningún valor concebible de O (x) por debajo del infinito, el tiempo tomado es probablemente correcto (si puede esperar tanto tiempo).

Answer 2

1 Coloque sus artículos para clasificarlos en tarjetas de índice
2 Lánzalos al aire en un día ventoso, a una milla de tu casa.
2 Tíralos a una hoguera y confirma que están completamente destruidos.
3 Verifique el piso de su cocina para el orden correcto.
4 Repita si no es el orden correcto.

El mejor caso es Scenerio O (∞)

Edite arriba basado en la observación astuta de KennyTM.

Answer 3

Aquí hay 2 tipos que se me ocurrió con mi compañero de cuarto en la universidad

1) Verifique el orden 2) Tal vez sucedió un milagro, vaya a 1

y

1) compruebe si está en orden, si no 2) coloque cada elemento en un paquete y repórtelo a un servidor distante. Algunos de esos paquetes regresarán en un orden diferente, así que vaya a 1

Answer 4

Bogobogosort. Sí, es una cosa. a Bogobogosort, usted Bogosort el primer elemento. Verifique si ese elemento está ordenado. Siendo un elemento, será. Luego agrega el segundo elemento y Bogosort los dos hasta que se clasifique. Luego agregas un elemento más, luego Bogosort. Continúa agregando elementos y Bogosorting hasta que finalmente hayas hecho todos los elementos. Esto fue diseñado para nunca tener éxito con ninguna lista importante antes de la muerte por calor del universo.

Answer 5

Bozo sort es un algoritmo relacionado que verifica si la lista está ordenada y, si no, intercambia dos elementos al azar. Tiene las mismas mejores y peores actuaciones, pero intuitivamente esperaba que el caso promedio fuera más largo que Bogosort. Es difícil encontrar (o producir) datos sobre el rendimiento de este algoritmo.

Answer 6

De la página de algoritmos esotéricos de David Morgan-Mar : diseño inteligente

Introducción

Intelligent design sort es un algoritmo de clasificación basado en la teoría del diseño inteligente.

Descripción del algoritmo

La probabilidad de que la lista de entrada original esté en el orden exacto en que está es de 1 / (n!). Hay una probabilidad tan pequeña de esto que es claramente absurdo decir que esto sucedió por casualidad, por lo que debe haber sido puesto conscientemente en ese orden por un clasificador inteligente. Por lo tanto, es seguro suponer que ya está ordenado de una manera óptima que trasciende nuestro ingenuo entendimiento mortal del "orden ascendente". Cualquier intento de cambiar ese orden para ajustarse a nuestras propias preconcepciones en realidad lo haría menos ordenado.

Análisis

Este algoritmo es constante en el tiempo y ordena la lista en el lugar, sin requerir memoria adicional. De hecho, ni siquiera requiere ninguna de esas cosas informáticas tecnológicas sospechosas. ¡Alabado sea el clasificador!

Realimentación

Gary Rogers escribe:

Hacer que el género sea constante a tiempo, niega el poder de The Sorter. The Sorter existe fuera del tiempo, por lo tanto, el género es intemporal. Para requerir tiempo para validar el orden, disminuye el papel del Clasificador. Por lo tanto ... este tipo particular es defectuoso, y no puede ser atribuido a ''The Sorter''.

¡Herejía!

Answer 7

Debería investigar el apasionante campo de los Algoritmos Pesimistas y el Análisis Simplexity . Estos autores trabajan en el problema de desarrollar un género con un mejor caso pésimo (el mejor caso de su bogosort es Omega (n), mientras que el orden lento (vea el papel) tiene una complejidad de tiempo mejor que el polinomio).

Answer 8

Doble bogosort

Bogosort dos veces y compare resultados (solo para asegurarse de que esté ordenado) si no lo hace de nuevo

Answer 9

Esta página es una lectura interesante sobre el tema: http://home.tiac.net/~cri_d/cri/2001/badsort.html

Mi favorito personal es sillysort de Tom Duff:

/*
 * The time complexity of this thing is O(n^(a log n))
 * for some constant a. This is a multiply and surrender
 * algorithm: one that continues multiplying subproblems
 * as long as possible until their solution can no longer
 * be postponed.
 */
void sillysort(int a[], int i, int j){
        int t, m;
        for(;i!=j;--j){
                m=(i+j)/2;
                sillysort(a, i, m);
                sillysort(a, m+1, j);
                if(a[m]>a[j]){ t=a[m]; a[m]=a[j]; a[j]=t; }
        }
}

Answer 10

Estoy sorprendido de que nadie haya mencionado el sueño todavía ... ¿O no lo he notado? De todas formas:

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

uso de ejemplo:

./sleepsort.sh 5 3 6 3 6 3 1 4 7
./sleepsort.sh 8864569 7

En términos de rendimiento, es terrible (especialmente el segundo ejemplo). Esperar casi 3,5 meses para ordenar 2 números es un poco malo.

Answer 11

Hace muchos años, inventé (pero nunca lo implementé realmente) MiracleSort.

Start with an array in memory.
loop:
    Check to see whether it''s sorted.
    Yes? We''re done.
    No? Wait a while and check again.
end loop

Eventualmente, las partículas alfa intercambiando bits en los chips de memoria deberían dar como resultado una clasificación exitosa.

Para mayor confiabilidad, copie la matriz en una ubicación blindada y verifique matrices potencialmente ordenadas contra la original.

Entonces, ¿cómo verificar la matriz potencialmente ordenada contra el original? Simplemente ordena cada matriz y verifica si coinciden. MiracleSort es el algoritmo obvio para usar en este paso.

EDITAR: Estrictamente hablando, esto no es un algoritmo, ya que no está garantizado que termine. ¿"No es un algoritmo" califica como "un peor algoritmo"?

Answer 12

Hay un tipo que se llama bogobogosort. Primero, verifica los primeros 2 elementos y los bogosorts. A continuación, comprueba los primeros 3, los bogosorts, y así sucesivamente. Si la lista está fuera de servicio en cualquier momento, se reinicia al bogosorting los primeros 2 nuevamente. Bogosort regular tiene una complejidad promedio de O (N!), Este algoritmo tiene una complejidad promedio de O (N! 1! 2! 3! ... N!) Editar: Para darle una idea de cuán grande es este número, para 20 elementos, este algoritmo toma un promedio de 3.930093 * 10 ^ 158 años, muy por encima de la muerte por calor propuesta del universo (si sucede) de 10 ^ 100 años, mientras que el tipo de fusión tarda alrededor de .0000004 segundos, tipo burbuja .0000016 segundos, y bogosort toma 308 años, 139 días, 19 horas, 35 minutos, 22.306 segundos, asumiendo que un año es 365.242 días y una computadora hace 250,000,000 operaciones enteras de 32 bits por segundo. Edit2: Este algoritmo no es tan lento como el tipo de algoritmo "milagro", que probablemente, como este tipo, succionará la computadora en el agujero negro antes de que ordene con éxito 20 elementos, pero si lo hiciera, estimaría una complejidad promedio de 2 ^ (32 (el número de bits en un entero de 32 bits) N) (el número de elementos) (un número <= 10 ^ 40 años, ya que la gravedad acelera las fichas en movimiento alfa, y hay 2 ^ N estados , que es 2 ^ 640 * 10 ^ 40, o aproximadamente 5.783 * 10 ^ 216.762162762 años, aunque si la lista comenzó ordenada, su complejidad sería solo O (N), más rápida que el tipo de fusión, que es solo N log N, incluso en el peor de los casos. Edit3: Este algoritmo es más lento que el tipo milagroso ya que el tamaño es muy grande, digamos 1000, ya que mi algoritmo tendría un tiempo de ejecución de 2.83 * 10 ^ 1175546 años, mientras que el algoritmo de ordenación milagrosa funcionaría tiempo de 1.156 * 10 ^ 9657 años.

Answer 13

Jingle Sort, como se describe here .

Le das a cada valor de tu lista a un niño diferente en Navidad. Los niños, siendo seres humanos horribles, compararán el valor de sus dones y se clasificarán de acuerdo a ellos.

Answer 14

Mi algoritmo de clasificación lento favorito es el tipo de títere:

void stooges(long *begin, long *end) {
   if( (end-begin) <= 1 ) return;
   if( begin[0] < end[-1] ) swap(begin, end-1);
   if( (end-begin) > 1 ) {
      int one_third = (end-begin)/3;
      stooges(begin, end-one_third);
      stooges(begin+one_third, end);
      stooges(begin, end-one_third);
   }
}

La peor de las complicaciones es O(n^(log(3) / log(1.5))) = O(n^2.7095...) .

¡Otro algoritmo de clasificación lento se llama en realidad slowsort!

void slow(long *start, long *end) {
   if( (end-start) <= 1 ) return;
   long *middle = start + (end-start)/2;
   slow(start, middle);
   slow(middle, end);
   if( middle[-1] > end[-1] ) swap(middle-1, end-1);
   slow(start, end-1);
}

Esta toma O(n ^ (log n)) en el mejor de los casos ... incluso más lento que stoogesort.

Answer 15

Nada puede ser peor que el infinito.

Answer 16

Puede hacer que cualquier algoritmo de ordenación sea más lento ejecutando el paso "¿Se ordenó?" Aleatoriamente. Algo como:

1. Cree una matriz de booleanos del mismo tamaño que la matriz que está ordenando. Ponlos todos en falso.
2. Ejecute una iteración de bogosort
3. Elige dos elementos aleatorios.
4. Si los dos elementos están ordenados en relación mutua (i <j && array [i] <array [j]), marque los índices de ambos en la matriz booleana en verdadero. En exceso, comienza de nuevo.
5. Compruebe si todos los booleanos en la matriz son verdaderos. Si no, regrese a 3.
6. Hecho.

Answer 17

Randomsubsetsort.

Dada una matriz de n elementos, elija cada elemento con probabilidad 1 / n, aleatorice estos elementos y verifique si la matriz está ordenada. Repita hasta que esté ordenado.

El tiempo esperado se deja como un ejercicio para el lector.

Answer 18

Sí, SimpleSort, en teoría se ejecuta en O(-1) sin embargo, esto es equivalente a O(...9999) que a su vez es equivalente a O (∞ - 1), lo que sucede es también equivalente a O (∞ ) Aquí está mi implementación de ejemplo:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}

Answer 19

Si mantiene el algoritmo significativo de cualquier manera, O(n!) Es el límite superior peor que puede lograr.

¡Ya que se verifica cada posibilidad de permutaciones de un conjunto que se va a ordenar tomará n! pasos, no puedes ser peor que eso.

Si está haciendo más pasos que eso, entonces el algoritmo no tiene un propósito realmente útil. Sin mencionar el siguiente algoritmo de clasificación simple con O(infinity) :

list = someList
while (list not sorted):
    doNothing

Answer 20

Siempre está el Bogobogosort (Bogoception!). Realiza Bogosort en subconjuntos cada vez más grandes de la lista, y luego comienza de nuevo si la lista no está ordenada.

for (int n=1; n<sizeof(list); ++n) {
  while (!isInOrder(list, 0, n)) {
    shuffle(list, 0, n);
  }
  if (!isInOrder(list, 0, n+1)) { n=0; }
}

Answer 21

Tuve un profesor que una vez sugirió generar una matriz aleatoria, verificar si estaba ordenada y luego verificar si los datos eran los mismos que la matriz que se ordenó.

Mejor caso O (N) (¡bebé por primera vez!) Peor caso O (Nunca)

Answer 22

Un rendimiento de peor caso de O (∞) podría incluso no convertirlo en un algoritmo según some .

Un algoritmo es solo una serie de pasos y siempre se puede mejorar ajustando un poco para obtener el resultado deseado en más pasos de lo que anteriormente se hacía. Uno podría poner a propósito el conocimiento de la cantidad de pasos realizados en el algoritmo y hacer que termine y produzca el resultado correcto solo después de que se hayan realizado X pasos. Que X podría ser del orden de O (n ² ) o O (n ^n! ) O lo que sea que el algoritmo deseara hacer. Eso aumentaría de manera efectiva su mejor caso así como los límites promedio de casos.

Pero su peor escenario no se puede superar :)

Answer 23

Uno en el que estaba trabajando implica elegir dos puntos al azar, y si están en el orden incorrecto, invertir todo el subrango entre ellos. Encontré el algoritmo en http://richardhartersworld.com/cri_d/cri/2001/badsort.html , que dice que el caso promedio es probablemente en algún lugar alrededor de O (n ^ 3) o O (n ^ 2 log n) ( él no está realmente seguro).

Creo que sería posible hacerlo de manera más eficiente, porque creo que sería posible realizar la operación de reversión en O (1) vez.

En realidad, me acabo de dar cuenta de que hacer eso podría hacer que todo lo que digo sea porque me di cuenta de que la estructura de datos que tenía en mente pondría acceso a los elementos aleatorios en O (log n) y determinaría si es necesario invertirlos en O (n )

Answer 24

Bogosort cuántico

Un algoritmo de clasificación que asume que la interpretación de muchos mundos de la mecánica cuántica es correcta:

1. Verifique que la lista esté ordenada. Si no, destruye el universo.

Al finalizar el algoritmo, la lista se ordenará en el único universo que queda en pie. Este algoritmo toma el peor caso O (N) y el tiempo promedio de O (1). De hecho, el número promedio de comparaciones realizadas es 2: hay un 50% de posibilidades de que el universo se destruya en el segundo elemento, un 25% de posibilidades de que se destruya en el tercero, y así sucesivamente.

Answer 25

Segmentos de π

Supongamos que π contiene todas las posibles combinaciones de números finitos. Ver pregunta math.stackexchange

1. Determine la cantidad de dígitos necesarios del tamaño de la matriz.
2. Use segmentos de π lugares como índices para determinar cómo reordenar la matriz. Si un segmento excede los límites de tamaño para este conjunto, ajuste el desplazamiento decimal π y comience nuevamente.
3. Compruebe si la matriz reordenada está ordenada. Si es molesto, de lo contrario ajuste la compensación y comience nuevamente.

Answer 26

Recursive Bogosort (probably still O(n!){
if (list not sorted)
list1 = first half of list.
list 2 = second half of list.
Recursive bogosort (list1);
Recursive bogosort (list2);
list = list1 + list2
while(list not sorted)
    shuffle(list);
}