¿Cuál es el mejor algoritmo de clasificación manual? Por ejemplo, si tuviera una pila de papeles que quisiera ordenar alfabéticamente, ¿cuál sería la forma más eficiente de hacerlo? ¿Qué pasaría si estuvieras de acuerdo con que uno o dos se alejen de su posición ordenada?

Puedes pensar en esto de una manera similar a ordenar en una computadora. Existen dos cuestiones de tiempo, que son aproximadamente las mismas tanto en el sistema humano como en el informático; y memoria, que se traduce aproximadamente a la cantidad de espacio de trabajo en la mesa o el piso que tiene. Sin embargo, en el mundo real, los humanos no son muy buenos para abordar estas ranuras de memoria en el tiempo O (1). Si bien las computadoras pueden acceder fácilmente a la 525a dirección de memoria, es mucho más difícil para un humano elegir una 525ta pila de papel en el suelo. Por lo tanto, en realidad hay un aumento en la complejidad del tiempo a medida que aumentan también los requisitos de “memoria”.

Entonces, hablemos de algoritmos específicos.

Ciertos tipos que funcionan bien computacionalmente simplemente no funcionan con las personas. Quicksort y heapsort, por ejemplo, simplemente no tienen sentido teniendo en cuenta las dificultades de direccionamiento mencionadas anteriormente.

Los tipos O (N ^ 2) que a menudo se descartan en realidad funcionan bastante bien, ya que el N es relativamente pequeño la mayor parte del tiempo cuando se clasifica el papel, y el acto de buscar linealmente a través de la pila de papeles, que la mayoría de esta clase de El algoritmo depende de, toma aproximadamente el mismo tiempo que abordar específicamente un subconjunto.

Los tipos de cubo realmente funcionan muy bien, ya que todavía podemos abordar relativamente rápido las 26 letras en inglés.

Definitivamente, hay clases recursivas que aún pueden funcionar bien cuando se clasifica a mano. Mergesort solo depende de la comparación entre dos objetos a la vez y de la fusión en una sola pila, por lo que funciona especialmente bien. Sin embargo, se necesita mucho espacio si sigue el algoritmo rigurosamente.

Finalmente, una combinación de tipos a menudo funciona mejor que simplemente apegarse a un solo algoritmo. La implementación de GNU de sort es una combinación de introsort (que en sí mismo es quicksort + heapsort) y de inserción. Entonces, en la práctica, descubrí que lo que funciona bien con pilas grandes (entre 300 y 1000 papeles) es dividir primero la pila en K subpilas, donde K es una potencia de dos, y cada sub-pila tiene menos de 100 hojas de papel Luego, cubra cada sub-pila alfabéticamente. La mayoría de los cubos deben ser pequeños, por lo que la selección o el orden de inserción pueden poner rápidamente cada cubo en orden. Una vez que se ordena cada sub-pila, comience a combinar pares por mergesort.