Tri d'une liste importante de test scores

Question

Vous avez une grande liste (disons N > 10000) des résultats des tests de laquelle vous souhaitez trier.Les résultats sont compris entre 1 et 100.Quel est le moyen le plus rapide pour trier la liste?

La première pensée.Nous avons un O(N log N) à destination, mais nous avons aussi plus d'informations sur les quantités dans le tableau, donc je pense que nous pourrions faire mieux.

Deuxième pensée:devrions-nous utiliser les tables de hachage, nous soucions-nous de doublons?Ne peux pas le voir comment utiliser les tables de hachage.

Troisième réflexion:est ce que cela a quelque chose à voir avec radix tri?aucune idée.

Quatrième réflexion:Pourrait-on classer cette liste par la création d'une autre liste, et puis passer par la fréquence de comptage des éléments s'est produite.Mais aurions-nous besoin d'un autre col à créer une plus grande liste triée, qui serait en O(N^2).ie trop grand.

Est-ce une très simple question ou une question difficile?

Answer 1

C'est une très simple question, en supposant que tous les scores sont des nombres entiers.

Ici est la plus simple de l'algorithme dans des termes simples.Nous allons lancer count, d'un tableau d'entiers de 100 zéros.Pour chaque score s, nous allons ajouter 1 à count[s].Pour produire le voulait triés scores, nous seront de sortie count[1] 1s, count[2] 2s, ..., et enfin count[100] 100s.

Ce type d'algorithme de tri est appelé le comptage de tri.

Le cas de plus de $N>10000$ tests qui sont entre 1 et 100 est un nombre premier de l'utilisation de comptage de tri.La complexité du temps est $O(N)$ et l'espace de la complexité est bornée par certains petits constante multiple de 100.

Vous voudrez peut-être vérifier comptage de tri pour plus d'informations.

Answer 2

Oui, en utilisant des algorithmes de tri comme la fusion, nous pouvons y parvenir par O (n * logn), nous pouvons faire mieux ici. Les informations supplémentaires données concernant la limité des scores de test sont très utiles ici.

faisons-nous des doublons?

Si nous traitons simplement des scores et que nous ne nous soucions pas des autres informations telles que Student_Name ou Subj.info et que nous voulons simplement que les scores sont au format triisé, vous pouvez utiliser cet algorithme.

     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.

Maintenant, si nous nous soucions de l'info si le score comme étudiant / sujet qu'il appartenait à utiliser cette approche ci-dessous. Je suppose que vous stockerez le score et les informations connexes dans une structure C / C ++ ou tout format d'objet.

Maintenant maintenant une table de hachage de taille 100 (gamme de scores de test) clé= score valeur= une liste d'objets ou d'instances avec ce score (si vous êtes Tri pour une liste des élèves, liste des élèves de ce score)

Si vous connaissez C / C ++, cette structure de données peut être implémentée à l'aide de la liste des listes liées. La technique de hachage utilisée ici est hachage séparé .

.

La fonctionnalité de la structure de données est comme celle-ci DS [Score] a le pointeur / référence à la liste liée Utilisation d'une autre carte de hachage pour identifier les queues de chaque sous-liste dans DS, nous pouvons insérer un nouvel élément dans O (1) heure.

donc dans un seul passage de i= 0 à i

Après avoir inséré, nous pouvons créer une nouvelle liste avec une seule passe sur DS que nous avons créée.

L'algorithme est comme ça.

Le tableau contient tous les objets avec leurs scores respectifs

    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.

Cette approche est par magie la forme de la base 100. En savoir plus sur Tri radix et compter Trier avec la mise en œuvre de la file d'attente.

de la question: "Quatrième pensée: Pourrions-nous trier cette liste en créant une autre liste, puis passez à travers les fréquences de comptage d'origine des éléments survenues. Mais auriez-nous besoin d'une autre passe pour créer une liste triée plus importante, qui serait O (n ^ 2). Ie trop grand. "

Je pense que vous vous trompez qu'un autre passage changerait N à N2. Sauf si vous placez le «autre laissez-passer» dans une boucle, il ne le fera pas.

J'espère avoir répondu à toutes vos questions.