Classificando uma grande lista de pontuações de testes

Question

Você tem uma lista grande (digamos N> 10.000) de pontuações de testes que gostaria de classificar.As pontuações dos testes estão entre 1 e 100.Qual é a maneira mais rápida de classificar a lista?

Primeiro pensamento.Temos um limite O(N log N), mas também temos informações adicionais sobre as quantidades na matriz, então acho que poderíamos fazer melhor.

Pensando melhor:devemos usar tabelas hash, nos preocupamos com duplicatas?Não consigo ver como usar tabelas hash.

Terceiro pensamento:isso tem algo a ver com a classificação radix?nenhuma idéia.

Quarto pensamento:Poderíamos classificar esta lista criando outra lista e, em seguida, passar pelas frequências de contagem originais dos elementos ocorridos.Mas precisaríamos de outra passagem para criar uma lista ordenada maior, que seria O(N^2).ou seja, muito grande.

Esta é uma pergunta muito fácil ou muito difícil?

Answer 1

Esta é uma pergunta muito fácil, assumindo que todas as pontuações são números inteiros.

Aqui está o algoritmo mais simples em palavras simples.Nós vamos iniciar count, uma matriz inteira de 100 zeros.Para cada pontuação s, adicionaremos 1 a count[s].Para produzir as pontuações classificadas desejadas, produziremos count[1] 1s, count[2] 2s, ... e finalmente count[100] 100s.

Esse tipo de algoritmo de classificação é chamado de classificação por contagem.

O caso de mais de $N>10.000$ pontuações de testes entre 1 e 100 são o principal uso da classificação por contagem.A complexidade do tempo é $O(N)$ e a complexidade do espaço é limitada por algum pequeno múltiplo constante de 100.

Você pode querer verificar classificação de contagem Para maiores informações.

Answer 2

Sim, usando algoritmos de classificação como classificação por mesclagem, podemos conseguir isso por O (N * logN), podemos fazer melhor aqui.As informações adicionais fornecidas sobre o limite das pontuações dos testes são muito úteis aqui.

nos preocupamos com duplicatas?

se estamos lidando apenas com pontuações e não nos importamos com outras informações, como student_name ou subject_info e queremos apenas as pontuações em formato classificado, você pode 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.

Agora, se nos preocupamos com as informações se a pontuação é como aluno/disciplina a que pertence, use a abordagem abaixo.presumo que você armazenará a pontuação e as informações relacionadas em uma estrutura c/c++ ou em qualquer formato de objeto.

Agora, mantenha uma tabela de hash do tamanho 100 (intervalo de pontuações de teste) key = Valor da pontuação = uma lista de objetos ou instâncias com essa pontuação (se você estiver classificando para uma lista de alunos, depois a lista de alunos com essa pontuação)

se você estiver familiarizado com c/c++, essa estrutura de dados pode ser implementada usando uma matriz de listas vinculadas. A técnica de hash usada aqui é hash separado.

A funcionalidade da estrutura de dados é como essa ds [pontuação] possui o ponteiro/referência à lista vinculada usando outro mapa de hash para identificar as caudas de cada sub-listas em DS, podemos inserir um novo elemento no tempo O (1).

então em uma única passagem de i = 0 para i

após inserir podemos criar uma nova lista com uma única passagem no DS que criamos.

o algoritmo é assim.

deixe o array conter todos os objetos com suas respectivas pontuações

    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.

essa abordagem magicamente é uma base baseada em fila, tipo base 100.Leia mais sobre classificação radix e classificação por contagem com implementação de fila.

da pergunta:"Quarto pensamento:Poderíamos classificar esta lista criando outra lista e, em seguida, passar pelas frequências de contagem originais dos elementos ocorridos.Mas precisaríamos de outra passagem para criar uma lista ordenada maior, que seria O(N^2).ou seja, muito grande."

acho que você está enganando que outra passagem mudaria N para Nˆ2 .a menos que você coloque a 'outra passagem' em um loop, isso não acontecerá.

espero ter respondido todas as suas perguntas.