Algoritmi di ordinamento rapido per array con elementi per lo più duplicati?

Question

Quali sono i modi efficienti per ordinare gli array che hanno per lo più una piccola serie di elementi duplicati? Cioè, una lista come:

{10, 10, 55, 10, 999, 8.851.243, 10, 55, 55, 55, 10, 999, 8.851.243, 10}

Supponendo che l'ordine di equal gli elementi non contano, quali sono gli algoritmi del caso peggiore/caso medio?

Answer 1

In pratica, è possibile prima eseguire un'iterazione attraverso l'array una volta e utilizzare una tabella hash per contare il numero di occorrenze dei singoli elementi (questo è O (n) dove n = dimensione dell'elenco). Quindi prendi tutti gli elementi univoci e ordinali (questo è O (k log k) dove k = numero di elementi univoci), e quindi espandi questo in un elenco di n elementi in passi O (n), recuperando i conteggi dal tabella hash. Se k < < n risparmi tempo.

Answer 2

IMO Pidgeonhole sort è un buon esempio per tali dati.

Chiarirò un po ': se sai che la quantità degli elementi unici nell'array è ragionevole e sai che ci sono molti duplicati, penserei di implementare qualcosa come il conteggio delle ordinazioni ma creare un elenco di "bucket" dinamico. Dopo il primo passaggio si elimineranno i duplicati, quindi si ordinerà l'array senza duplicati con un buon algoritmo di ordinamento e quindi si ripristinerà l'array ordinato in un modo simile al conteggio dell'ordinamento.

Answer 3

Non il migliore algoritmo, ma semplice:
Puoi mettere tutto in un trie e avere le foglie come contatori. Questo dovrebbe prendere O (n * m) dove n è il numero di elementi e m è la dimensione dell'elemento più grande (in genere sarebbe una costante, ma non necessariamente). Quindi pre-ordine attraversa la cravatta, emettendo gli elementi della chiave corrente quando colpisci una foglia. Questo dovrebbe richiedere solo O (n + p) dove p è la dimensione del trie, che dovrebbe essere piccola rispetto a n.

Answer 4

Proverei Counting sort con una funzione di mappatura. Vale a dire. non userete l'array di frequenze di dimensioni uguali all'intervallo di elementi, invece dovreste scorrere l'array, annotare elementi distinti e usarli in una funzione di mappatura per l'array di frequenze.

In questo modo l'algoritmo ha solo un'ulteriore iterazione e una funzione di mappatura, che dovrebbe funzionare in un tempo costante (utilizzando alcuni re della tabella hash). La complessità di questo approccio sarebbe O(n), che dovrebbe essere ottimale.

Answer 5

implementazione in C++ sulla base di algo come suggerito da @Antti Huima

• frequenze contare e conservare in tabella hash.
• ordina elementi nella tabella hash.

• sovrascrive l'array di input con elementi ordinati a seconda delle frequenze.

  #include <unordered_map> 
  #include <map> 
  // Modifies input array to a sorted array 
  // Complexity: O(n+(k*log(k))) where 'k' = number of unique elements input array 
  template <typename Datatype> 
  void SortArrayWithDuplicates(std::vector<Datatype>& in_seq) { 
      std::unordered_map<Datatype, int> key_counts_map; 
      // Count freqs O(n) 
      for (const auto& itr: in_seq) 
       key_counts_map[itr] += 1; 
  
      // Sort elements by inserting into a map O(k*log(k)) 
      std::map<Datatype, int> key_counts_sorted_map; 
      for (auto const& itr: key_counts_map) 
       key_counts_sorted_map.insert(std::make_pair(itr.first, itr.second)); 
  
      auto AlwaysTrue = [](Datatype i)->bool{return true;}; 
      auto seq_itr = std::begin(in_seq); 
      // Update input sequence with new sorted values 
      for (auto const& itr: key_counts_sorted_map) { 
       std::replace_if(seq_itr, seq_itr+itr.second, AlwaysTrue, itr.first); 
       seq_itr += itr.second; 
      } 
  }