¿Cuál es el algoritmo de clasificación más oscuro que conoces? [cerrado]

22

Acabo de leer sobre cyclesort a través de una publicación de blog de sortvis.org. Este es probablemente el más oscuro que he escuchado hasta ahora, ya que utiliza matemáticas con las que no estoy familiarizado (detección de ciclos en permutaciones de conjuntos enteros).

¿Cuál es el más oscuro que conoces?

sova
fuente
44
Debe volver a leer.
Mark C
Buen momento con esto, mi clase de estructuras de datos acaba de comenzar a cubrir tipos. Ahora, no solo entiendo los tipos básicos, sino también los locos.
Jason

Respuestas:

9

¿Has oído hablar de la paciencia ordenando ? Bueno ahora tienes ...

Mason Wheeler
fuente
1
Interesante, Bazar lo usa para resolver fusiones.
Tim Post
12

Slowsort funciona multiplicando y rindiendo (en lugar de dividir y conquistar). Es interesante porque es probablemente el algoritmo de clasificación menos eficiente que se puede construir (asintóticamente y con la restricción de que dicho algoritmo, aunque sea lento, debe estar trabajando todo el tiempo para obtener un resultado).

Esto lo compensa de bogosort porque, en el mejor de los casos, bogosort es bastante eficiente, es decir, cuando la matriz ya está ordenada. Slowsort no "sufre" de un comportamiento tan favorable. Incluso en su mejor caso, todavía tiene tiempo $ \ Omega (n ^ \ frac {\ log_2n} {2+ \ epsilon}) $ de ejecución para ϵ > 0.

Aquí está su pseudocódigo, adaptado del artículo alemán de Wikipedia :

function slowsort(A, i, j):
  if i >= j: return

  m = (i + j) / 2
  slowsort(A, i, m)
  slowsort(A, m + 1, j)

  if A[j] < A[m]:
    swap(A[j], A[m])

  slowsort(A, i, j - 1)
Konrad Rudolph
fuente
1
Bogosort puede hacerse trivialmente más pesimista en el mejor de los casos invirtiendo el orden de sus pasos: primero, barajar. Si está ordenado, deténgase.
Alex Feinman
3
@Alex: no. Eso no cambia nada. Bogosort aún estaría terminado después del primer paso porque, por casualidad, la combinación habría ordenado la secuencia. Bogosort todavía exhibe un comportamiento pronunciado en el mejor de los casos con un tiempo de ejecución fundamentalmente diferente (O (n)) de su peor caso y el caso promedio. Slowsort simplemente no tiene esto.
Konrad Rudolph
¡Ah, estaba pensando solo en las condiciones iniciales, no en las rutas de ejecución!
Alex Feinman
Amo esto :) Nada como la fuerza bruta ...
8

No sé si esto cuenta como oscuro, pero uno de los "algoritmos" de clasificación más ridículos es Bogosort . Los enlaces de la página de Bogosort también son divertidos.

Y está esta gema de la sección sobre "cuántica bogo-sort"

Podría decirse que crear universos de 2 N también requiere mucha memoria.

Hmmm ... se podría decir que :-).

Stephen C
fuente
Me gusta este. Me gusta especialmente la idea de "Quantum bogosort" :-)
Dean Harding
6

Otro "algoritmo" oscuro es la clasificación de diseño inteligente , pero ningún algoritmo es más rápido o tiene menos consumo de memoria :)

Caspar
fuente
Una de las mejores características de ese algoritmo es que sabemos que funciona: no es necesario analizar ni probar nada.
Caleb
6

Sleep Sort es bastante novedoso.

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

ejemplo de uso:

    ./sleepsort.bash 5 3 6 3 6 3 1 4 7
Mike Weller
fuente
5

Creo que el tipo de burbuja también sería la respuesta incorrecta en esta situación

:)

OscarRyz
fuente
3

Knuth Volume 3 1 , en la respuesta a uno de los ejercicios, ofrece una implementación de un algoritmo de clasificación sin nombre que es básicamente un antiguo código de golf: el tipo más corto que puede escribir en lenguaje ensamblador MIX. Sin embargo, el código corto tiene el precio tan bajo de la complejidad de O (N 3 ) ...

1 Al menos en las ediciones anteriores. Dadas las modificaciones a MIXAL para la nueva edición, no estoy seguro de si todavía está allí, o incluso tiene el minúsculo sentido en el MIXAL original.

Jerry Coffin
fuente
3

Para mi clase de estructuras de datos, tuve que (explícitamente) probar la corrección del tipo Stooge . Tiene un tiempo de ejecución de O (n ^ {log 3 / log 1.5}) = O (n ^ 2.7095 ...).

Alex ten Brink
fuente
2

No sé si es el más oscuro, pero el tipo de espagueti es uno de los mejores en situaciones donde puedes usarlo.

Caleb
fuente
Esta idea es bastante similar a la "clasificación del sueño" y, curiosamente, se utiliza en bioinformática para secuenciar el ADN (secuenciación de Sanger).
Konrad Rudolph
2

Uno de los libros originales de Knuth, "Ordenar y buscar", tenía un plegado central que esquematizaba un proceso que clasificaba un archivo de cinta sin disco duro. Creo que usó seis unidades de cinta y mostró explícitamente cuándo se leía cada una hacia adelante, se leía hacia atrás, rebobinando o inactiva. Hoy es un monumento a una tecnología obsoleta.

Andy Canfield
fuente
1

Una vez hice una clasificación de burbujas en registros vectoriales en el ensamblador CRAY. La máquina tenía una instrucción de doble cambio, que le permitía cambiar el contenido de un registro vectorial hacia arriba / abajo por una palabra. Ponga el otro punto en dos registros de vectores, luego podría hacer una clasificación de burbuja completa sin tener que hacer otra referencia de memoria hasta que haya terminado. Excepto por la naturaleza N ** 2 del tipo burbuja, fue eficiente.

También una vez tuve que hacer un tipo de coma flotante de un vector de longitud 4 lo más rápido posible para un solo tipo. Lo hice por búsqueda de tabla (el bit de signo de A2-A1 es un bit, el signo de A3-A1 forma otro bit ..., luego buscas el vector de permutación en una tabla. En realidad, fue la solución más rápida que pude encontrar Sin embargo, no funciona bien en arquitecturas modernas, las unidades flotantes y enteras están demasiado separadas.

Omega Centauri
fuente
¿Todavía tienes la fuente de esto? ¡Me interesaría echarle un vistazo!
sova
Sin fuente, fue para una máquina no obsoleta para una empresa que finalmente me despidió. La búsqueda en la tabla no es difícil: sb1 = 1 & ((a2-a1) >> 63); sb2 = 2 & ((a3-a1) >> 62); ... index = sb1 | sb2 | sb3 ... seguido por una tabla de búsqueda de la orden.
Omega Centauri
1

Google Code Jam tenía un problema con un algoritmo llamado Gorosort, que creo que inventaron para el problema.

Goro tiene 4 brazos. Goro es muy fuerte. No te metas con Goro. Goro necesita ordenar una matriz de N enteros diferentes. Los algoritmos no son la fuerza de Goro; La fuerza es la fuerza de Goro. El plan de Goro es usar los dedos en dos de sus manos para mantener presionados varios elementos de la matriz y golpear la mesa con sus puños tercero y cuarto lo más fuerte posible. Esto hará que los elementos no seguros de la matriz vuelen por el aire, se barajen al azar y vuelvan a caer en las ubicaciones de la matriz vacía.

http://code.google.com/codejam/contest/dashboard?c=975485#s=p3

MatrixFrog
fuente
0

No recuerdo el nombre, pero básicamente era

while Array not sorted

  rearrange the array in a random order
Akash
fuente
Esto es bogosort, mencionado en otras respuestas.
MatrixFrog
0

Tipo de concha

Tal vez el algoritmo en sí no sea tan oscuro, pero ¿quién puede nombrar una implementación que realmente se usa en la práctica? ¡Yo puedo!

TIGCC (un compilador basado en GCC para calculadoras gráficas TI-89/92 / V200) usa el ordenamiento Shell para la qsortimplementación en su biblioteca estándar:

__ATTR_LIB_C__ void qsort(void *list, short num_items, short size, compare_t cmp_func)
{
  unsigned short gap,byte_gap,i,j;                
  char *p,*a,*b,temp;                       
  for (gap=((unsigned short)num_items)>>1; gap>0; gap>>=1)    // Yes, this is not a quicksort,
    {                                                         // but works fast enough...    
      byte_gap=gap*(unsigned short)size;
      for(i=byte_gap; i<((unsigned short)num_items)*(unsigned short)size; i+=size)
        for(p=(char*)list+i-byte_gap; p>=(char*)list; p-= byte_gap)
          {
            a=p; b=p+byte_gap;
            if(cmp_func(a,b)<=0) break;
            for(j=size;j;j--)
              temp=*a, *a++=*b, *b++=temp;
          }
    }
}

Se seleccionó la ordenación de shell a favor de quicksort para mantener bajo el tamaño del código. Aunque su complejidad asintótica es peor, la TI-89 no tiene mucha RAM (190K, menos el tamaño del programa y el tamaño total de las variables no archivadas), por lo que es algo seguro asumir que la cantidad de elementos estar bajo

Se escribió una implementación más rápida después de que me quejé de que era demasiado lenta en un programa que estaba escribiendo. Utiliza mejores tamaños de espacio, junto con optimizaciones de ensamblaje. Se puede encontrar aquí: qsort.c

Joey Adams
fuente