Ordinamento di un ampio elenco di punteggi dei test

Question

Hai un lungo elenco (diciamo N > 10000) di punteggi dei test che desideri ordinare.I punteggi del test sono compresi tra 1 e 100.Qual è il modo più rapido per ordinare l'elenco?

Primo pensiero.Abbiamo un limite O(N log N), ma abbiamo anche informazioni aggiuntive sulle quantità nell'array, quindi penso che potremmo fare meglio.

Secondo pensiero:dovremmo usare le tabelle hash, ci preoccupiamo dei duplicati?Non riesco a vedere come utilizzare le tabelle hash.

Terzo pensiero:ha qualcosa a che fare con l'ordinamento digitale?nessuna idea.

Quarto pensiero:Potremmo ordinare questo elenco creando un altro elenco e quindi passare attraverso le frequenze di conteggio originali degli elementi che si sono verificati.Ma avremmo bisogno di un altro passaggio per creare un elenco ordinato più ampio, che sarebbe O(N^2).cioè troppo grande.

È una domanda molto facile o una domanda molto difficile?

Answer 1

Questa è una domanda molto facile, supponendo che tutti i punteggi siano numeri interi.

Ecco l'algoritmo più semplice in parole semplici.Iniziamo count, una matrice intera di 100 zeri.Per ogni punteggio s, aggiungeremo 1 a count[s].Per produrre i punteggi ordinati desiderati, emetteremo count[1] 1s, count[2] 2S, ... e infine count[100] 100s.

Questo tipo di algoritmo di ordinamento è chiamato il conto del conteggio.

il caso di più di $ n> 10000 $ punteggi del test compreso tra 1 e 100 è un utilizzo principale di un uso di conteggio.La complessità del tempo è $ o (n) $ e la complessità spaziale è delimitata da un piccolo piccolo multiplo costante di 100.

Potresti voler controllare contando ordinamento per ulteriori informazioni.

Answer 2

Sì, utilizzando algoritmi di ordinamento come Merge Sort possiamo ottenere questo risultato con O(N*logN), qui possiamo fare meglio.Le informazioni aggiuntive fornite riguardo al limite dei punteggi dei test sono molto utili in questo caso.

ci preoccupiamo dei duplicati?

se abbiamo a che fare solo con i punteggi e non ci interessano le altre informazioni come nome_studente o informazioni_soggetto e vogliamo solo i punteggi in formato ordinato, puoi utilizzare questo 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.

Ora, se ci interessano le informazioni se il punteggio come studente/materia a cui apparteneva, utilizzare questo approccio di seguito.presumo che memorizzerai il punteggio e le informazioni correlate in una struttura c/c++ o in qualsiasi formato oggetto.

Ora mantieni una tabella hash della dimensione 100 (intervallo di punteggi di test) tasto = valore del punteggio = un elenco di oggetti o istanze con questo punteggio (se stai ordinando per un elenco di studenti, quindi un elenco di studenti con questo punteggio)

se hai familiarità con c/c++, questa struttura dati può essere implementata utilizzando una serie di elenchi collegati. La tecnica di hashing utilizzata qui è hashing separato.

La funzionalità della struttura dei dati è come questo DS [punteggio] ha il puntatore/riferimento all'elenco collegato usando un'altra mappa hash per identificare le code di ciascuna sotto-list in DS che possiamo inserire un nuovo elemento in O (1) tempo.

quindi in un unico passaggio da i = 0 a i

dopo l'inserimento possiamo creare una nuova lista con un solo passaggio sul DS che abbiamo creato.

l'algoritmo è così.

let array contiene tutti gli oggetti con i rispettivi punteggi

    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.

questo approccio magicamente è una sorta di radice basata su coda di base 100.Ulteriori informazioni sull'ordinamento digitale e sull'ordinamento con conteggio con l'implementazione della coda.

dalla domanda:"Quarto pensiero:Potremmo ordinare questo elenco creando un altro elenco e quindi passare attraverso le frequenze di conteggio originali degli elementi verificatisi.Ma avremmo bisogno di un altro passaggio per creare un elenco ordinato più ampio, che sarebbe O(N^2).cioè troppo grande."

penso che tu stia sbagliando un altro passaggio cambierebbe N in Nˆ2.a meno che tu non stia inserendo "un altro passaggio" in un ciclo, non lo farà.

spero di aver risposto a tutte le tue domande.