Algoritmos de clasificación rápida para matrices con elementos mayormente duplicados?

Question

¿Cuáles son formas eficientes de ordenar matrices que tienen principalmente un pequeño conjunto de elementos duplicados? Es decir, una lista como:

{10, 10, 55, 10, 999, 8851243, 10, 55, 55, 55, 10, 999, 8851243, 10}

Suponiendo que el orden de equal los elementos no importan, ¿cuáles son los mejores algoritmos de peor caso/caso medio?

Answer 1

En la práctica, primero puede iterar a través de la matriz una vez y usar una tabla hash el recuento de la cantidad de ocurrencias de los elementos individuales (esto es O (n) donde n = tamaño de la lista). A continuación, tome todos los elementos únicos y ordénelos (esto es O (k log k) donde k = número de elementos únicos), y luego vuelva a expandir esto a una lista de n elementos en O (n) pasos, recuperando los recuentos del tabla de picadillo. Si k < < n ahorra tiempo.

Answer 2

IMO Pidgeonhole sort es un buen ejemplo para tales datos.

Aclararé un poco: si sabes que la cantidad de elementos únicos en la matriz es razonable y sabes que hay muchos duplicados, pensaría en implementar algo así como contar el tipo pero hacer una lista de "cubos" dinámica. Después del primer pase eliminarás los duplicados, luego ordenarás el conjunto sin duplicados con algún buen algoritmo de ordenación y luego restaurarás el conjunto ordenado de una manera como lo hace el conteo de ordenaciones.

Answer 3

No es el mejor algoritmo, pero simple:
Puede poner todo en un trie y hacer que las hojas sean contadores. Eso debería tomar O (n * m) donde n es el número de elementos ym es el tamaño del elemento más grande (típicamente eso sería una constante, pero no necesariamente). A continuación, realice un pedido por adelantado para atravesar la atadura y obtenga counter elementos de la tecla actual cuando toque una hoja. Eso debería tomar solo O (n + p) donde p es el tamaño del trie, que debe ser pequeño en comparación con n.

Answer 4

Probaría Counting sort con alguna función de mapeo. Es decir. no utilizará la matriz de frecuencias de un tamaño igual al rango de elementos, en su lugar, iterará sobre la matriz, anotará los distintos elementos y los utilizará en una función de mapeo para la matriz de frecuencias.

De esta forma, el algoritmo tiene solo una iteración extra y una función de mapeo, que debería funcionar en un tiempo constante (usando alguna tabla king de hash). La complejidad de este enfoque sería O(n), que debería ser óptima.

Answer 5

Implementación en C++ basado en algo como lo sugiere @Antti Huima

• frecuencias de recuento y se guardan en la tabla hash.
• ordenar elementos en hashtable.

• sobrescribe la matriz de entrada con elementos ordenados según las frecuencias.

  #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; 
      } 
  }