Ordenar una gran lista de puntajes de prueba

Question

Tiene una lista grande (Diga N> 10000) de las puntuaciones de los exámenes que le gustaría ordenar.Los puntajes de las pruebas están entre 1 y 100. ¿Qué es lo más rápido de ordenar la lista?

Pensamiento primero.Tenemos un límite de O (N) O (n), pero también tenemos información adicional sobre las cantidades en la matriz, así que creo que podríamos hacerlo mejor.

Segundo pensamiento: ¿Debemos usar tablas hash, nos preocupamos por los duplicados?No puedo ver cómo usar tablas hash.

Tercer pensamiento: ¿Tiene esto algo que ver con la clasificación de Radix?ninguna idea

Cuarto Pensamiento: ¿Podríamos ordenar esta lista al crear otra lista y luego pasar a través de las frecuencias de conteo originales de los elementos ocurridos?Pero necesitaríamos otro pase para crear una lista ordenada más grande, que sería O (n ^ 2).es decir, demasiado grande.

¿Es esta una pregunta muy fácil o una pregunta muy difícil?

Answer 1

Esta es una pregunta muy fácil, asumiendo que todas las puntuaciones sean enteros.

Aquí está el algoritmo más simple en palabras simples.Iniciaremos count, una variedad entera de 100 ceros.Para cada puntaje s, agregaremos 1 a count[s].Para producir las puntuaciones ordenadas deseadas, generaremos count[1] 1s, count[2] 2s, ..., y finalmente count[100] 100s.

Este tipo de algoritmo de clasificación se llama ordenar.

El caso de más de $ n> 10000 $ las puntuaciones de prueba que están entre 1 y 100 es un uso principal de la ordenación de conteo.La complejidad del tiempo es $ o (n) $ y la complejidad del espacio está limitada por algunos pequeños constantes múltiples de 100.

Es posible que desee comprobar Contando ordenar para más información.

Answer 2

Sí, usando algoritmos de clasificación como Merge Sleed Podemos lograr esto por O (n * LOGN) Podemos hacerlo mejor aquí. La información adicional dada con respecto al límite de los puntajes de las pruebas es muy útil aquí.

¿Nos importa los duplicados?

Si estamos tratando con solo puntajes y no le importa la otra información como Student_Name o Toming_Info y simplemente queremos las puntuaciones en formato ordenado, puede usar este algoritmo.

     maintain a int table[101] = {0}   - hash table with key as score
                        //all elements are initialised to 0

    array contains all scores
    for score in array
         table[score] = table[score] +1
         //above in O(N) time and O(1) space.

    sorted_list = {} // initially empty
    for (score= 0; score < 101;i++)
      for(count = 0; count < table[i]; count++)
          sorted_list.add(score)
          //the above runs in O(N) time and O(N) space.

Ahora, si nos importa la información, si el puntaje, como el estudiante / sujeto que pertenecía a usar este siguiente enfoque. Supongo que almacenará la puntuación y la información relacionada en una estructura C / C ++ o cualquier formato de objeto.

Ahora mantén una tabla de hash de tamaño 100 (rango de puntajes de prueba) clave= puntuación Valor= una lista de objetos o instancias con esta puntuación (si está Ordenar para una lista de estudiantes, entonces lista de estudiantes con esta puntuación)

Si está familiarizado con C / C ++, entonces esta estructura de datos se puede implementar utilizando la matriz de listas vinculadas. La técnica de hashing que se usa aquí es Hashing (strong>.

La funcionalidad de la estructura de datos es así DS [Puntuación] tiene el puntero / referencia a la lista vinculada Usando un mapa de hash para identificar las colas de cada sub-listas en DS, podemos insertar un nuevo elemento en el tiempo O (1).

así en una sola pasada de i= 0 a i

Después de insertar, podemos crear una nueva lista con una sola pasada en DS que hemos creado.

El algoritmo es así.

Deja que la matriz contenga todos los objetos con sus respectivas puntuaciones

    for (i = 0; i< n; i++)
      key = array[i].score
      DS[key].insert(array[i]) //the tail part can be used for O(1) insertion.

     //the above loop runs in O(N)

     sorted_list = {} // empty_list
     for(score = 1; score<=100;score++)
       for each (obj in DS[score]) 
          sorted_list.add(obj)

      //the above loop runs in O(N).

     //the N refers to the size of original list here.

Este enfoque es mágicamente, es una serie de radix basada en cola 100. Lea más sobre Radix Ordenar y contar ordenar con la implementación de la cola.

de la pregunta: "Cuarto pensamiento: podríamos ordenar esta lista al crear otra lista, y luego pasar a través de las frecuencias de conteo originales de los elementos ocurridos. Pero necesitaríamos otro pase para crear una lista ordenada más grande, que sería O (N ^ 2). IE demasiado grande ".

Creo que estás confundiendo Otro pase cambiaría N a N2. A menos que esté colocando el 'otro pase' en un bucle no.

Espero haber respondido todas sus preguntas.