El mejor algoritmo para ordenar los exámenes

Question

Soy un alumno de un curso de estadística y tengo una serie de tareas de papel asignadas en orden aleatorio. Parte de mi trabajo es alfabetizarlos. He estado usando un método similar al de clasificación rápida, pero otros alumnos han usado diferentes métodos. Quiero un método de ordenación eficiente, con justificación, porque cuando tengo un número "grande" de los exámenes, la justificación presentada .. Aquí hay algunos detalles que he apalancadas:

• tengo una lista que contiene una lista ordenada alfabéticamente de todos los nombres que debería ver
• No me interesa que los nombres estén más alfabetizados que la primera letra. Por ejemplo, estoy bien si "Smith, John" viene antes que "Salk, Jonas".
• Nunca tendré que ordenar más de 300 objetos.

Mi método hasta ahora ha sido encontrar la última letra mediana (es decir, si hay 60 documentos, elija la última letra correspondiente a la persona 30) de la lista de la clase, trátela como un punto de pivote, y coloque todas las letras encima de la mediana en una pila, y todas las letras debajo en otra. Si una letra es la misma que la mediana, la coloco en la pila mediana. Ahora hago lo mismo en las pilas arriba/debajo de la mediana. Cuando las pilas son lo suficientemente pequeñas como para que solo haya tres o cuatro letras en una pila, hago una pila para cada letra, luego doblo las pilas en una pila maestra, alfabéticamente.

¿Hay algún algoritmo específicamente diseñado para la alfabetización, o algo que sea más eficiente en promedio que mi método? Un método que parecía funcionar bien era hacer una pila para cada letra (26 montones, en el peor de los casos), pero esto consume tanto espacio que no es factible para un escritorio.

Answer 1

Estaba mirando alrededor de algunos sitios web que hablaban de algoritmos para que los humanos los usen, y uno que vi estaba haciendo una especie de ordenamiento de inserción, donde pones el que está en la mano poniéndolo directamente donde está el orden correcto debería ser.

La ineficacia de esto probablemente sería por tener que escanear la pila para encontrar la ubicación a medida que la pila se hace más grande, así que estoy pensando que para ajustar esto, puede agregar una etiqueta o algo que actúe como un índice para una ubicación alfabética específica. Ya que no le importa el orden alfabético aparte de la primera letra, esto básicamente pondría su costo de inserción en O (1)

Esto es solo un pensamiento que tuve mientras pensaba en ello, así que no lo he intentado en realidad yo mismo, y no puedo decir con respecto a cuán efectivo sería con pilas lo suficientemente grandes. Pero creo que debería funcionar bastante bien, ya que las etiquetas le daría acceso instantáneo a la ubicación que desea insertar.

Answer 2

Quicksort probablemente no sea el mejor, ya que su eficacia depende de la opción de pivote. De todos modos, con solo 300 exámenes lo que haría sería crear 26 pilas (una para cada letra) y solo hacer una pasada para todos los exámenes colocándolas en las pilas apropiadas

Answer 3

Su último párrafo es ordenar por inserción. Si 26 pilas son dos muchas, use 24 :). Si 26 pilas son demasiadas, divida el alfabeto y los exámenes en 5 pilas. Luego clasifique cada pila, nuevamente tendrá 5 cajas (una con 6).

Answer 4

Uso el tipo de cuchara. Use cuatro cubos y vuelva a clasificar cada cubeta con otra clasificación de 4 cubos, ¡clasifique cada cubeta secundaria (1/16) por fuerza bruta!

Answer 5

• especie en la primera letra en M pilas
• vez que necesita> = M pilas: poner todos los elementos con que no encaja, comenzará letras en un bote de basura-pila
• al final de la primera ejecución M las pilas están completos
• Recurse, utilizando las sobras de la pila de basura

la constante M se puede ajustar para que coincida con su capacidad para m atch & poner letras múltiples a primera vista. (y el espacio de escritorio disponible)

En la práctica, no necesitará más de unas pocas ejecuciones, para valores razonables de M. (Ley de Zipf/Pareto)

Answer 6

He basado mi algoritmo en la premisa de que el tiempo que me lleva determinar el orden correcto para dos elementos no es consistente. Por ejemplo, es fácil para mí decir que A pertenece antes que D, pero me lleva a decidir si Q viene antes de T o viceversa (en general, cuanto más cerca están las letras del alfabeto y entre ellas, más lo más probable es que tendré que recitar mentalmente el alfabeto para estar seguro).

Teniendo en cuenta esto, me parece que disminuye las tediosas "trozos" del alfabeto-recitar si divido las pruebas en orden alfabético:

• Comenzando (ish AF)
• medio temprano (GK ish)
• Centro tardío (LP ish)
• Fin (QZ ish). Este es más grande porque (a) es el sector en el que soy peor para decidir sobre el orden de las letras y (b) algunas de estas letras no suelen comenzar con los apellidos

Hay superposición - es decir a veces siento que una Q es Late Middle y a veces siento que es End. Depende de cuán grandes son las pilas en ese punto y qué letra ordené por última vez ... mi teoría es que el tiempo ahorrado al no deletrear el alfabeto en mi cabeza todo el tiempo es mayor que el tiempo extra dedicado a ordenar más tarde en.

Eso es todo lo que he conseguido, sin embargo. Más allá de la fragmentación inicial, nunca puedo decidir qué es lo más eficiente ...

Answer 7

¡Esta es una gran pregunta! Llevamos a cabo un pequeño experimento para acercarnos a una respuesta.

Nuestro set-up consistió en

• 3 clasificadores (A, B y C).

• 3 pilas de 40 conjuntos de problemas para el alumno (uno para cada clasificador). El número de hojas de un conjunto de problemas varió de 1 a 5. Las hojas se graparon y los nombres de los estudiantes se escribieron en la parte superior de la primera página.

• 3 algoritmos de ordenación para ordenar alfabéticamente las pilas:

  • inserción: Tome la parte superior de la pila artículo sin clasificar y se insertan en la posición correcta en la pila ordenada. Se permite desplegar la pila clasificada.
  • Cubo: Clasifique cada elemento en uno de los cinco cubos (A-E, F-J, K-O, P-T, U-Z). Luego, clasifique cada cubo usando la ordenación por inserción. Combina los cubos clasificados
  • Merge: Divida los artículos en 10 pilas. Clasifica cada pila usando clasificación por inserción. Pon 10 pilas ordenadas en 5 pares. Combina cada par mirando repetidamente los elementos superiores del par y colocando el más alto alfabéticamente en la parte inferior de la pila resultante del par. Después de fusionar 10 pilas en 5, fusiona 2 de las 5 pilas, de modo que quedan 4 pilas. Luego, se fusiona repetidamente en pares hasta que quede una sola pila ordenada.

• Medidas:

  • Tiempo hasta la finalización del algoritmo de ordenación.
  • Número de elementos extraviados (medidos por otro clasificador).

• El orden de los algoritmos de ordenamiento se asignó al azar.

• Cada ronda nueva las pilas del conjunto de problemas se intercambiaban entre clasificadores y se mezclaban durante varios minutos.

• Los clasificadores A y B hicieron cada uno 9 rondas, el clasificador C hizo 3 rondas.

• Se colocó una hoja con los valores de corte del alfabeto y del cubo en la tabla de cada clasificador.

Aquí está una imagen de nuestra configuración.

Y aquí están los resultados.

Dos conclusiones son inmediatos.

1. El algoritmo de ordenación de fusión relativamente complejo se preparó mal. Los géneros de fusión han tardado de un 57 a un 125% más que en los promedios de clasificación de cubetas/inserciones de clasificadores sin ganancias obvias de precisión.

Creemos que el paso inicial de dividir por primera vez la pila de conjuntos de problemas en 10 montones puede contribuir a fusionar los resultados deslucidos de la clase. Los futuros investigadores pueden encontrar que los algoritmos fusionados combinados con procedimientos de configuración más eficientes son efectivos.

2. Aunque la clasificación del cucharón y la inserción funcionaron bien, la clasificación del cucharón fue de un 13 a un 25% más rápida que la ordenación por inserción dentro de los clasificadores. Esta diferencia corresponde a aproximadamente un minuto de tiempo guardado para cada clasificación de 40 grupos de problemas.

Especulamos que la eficiencia relativa de cubo de tipo mejoraría como el número de conjuntos de problemas para ordenar crece por encima de 40 y que la ordenación por inserción dominaría para pilas de 30 o menos, aunque se necesitan más pruebas. No hubo diferencias claras en la precisión entre el cubo y los géneros de inserción.

Por último, observamos que existen importantes diferencias individuales en la capacidad de clasificación entre nuestros sujetos de prueba. El Clasificador B superó consistentemente a los clasificadores A y C en un promedio de 39 y 101 segundos, respectivamente. Esto sugiere que, aunque el procedimiento de clasificación empleado es importante para la velocidad de clasificación, la capacidad puede explicar al menos una gran parte de la varianza en los resultados individuales. Explorar lo que hace a los alemanes clasificadores tan fantásticos es un área prometedora para futuras investigaciones.

Answer 8

Mi departamento tiene un curso básico con típicamente 500-600 estudiantes que están escribiendo el examen. Desde un punto de vista de error & parece que obtenemos la ordenación más rápida primero haciendo una clasificación de cubo con aproximadamente un cubo por letra. La letra S normalmente se puede dividir en dos cubos, mientras que las letras al final del alfabeto (x, y, z) generalmente pueden compartir una cubeta. Luego ordenamos dentro de cada cubeta por clasificación de inserción y terminamos apilando los cubos.

Para clases pequeñas (hasta alrededor de 30) la clasificación por inserción directa es viable, pero el tiempo requerido para encontrar la posición correcta para insertar rápidamente se va de las manos cuando la pila crece.