ほとんどの要素が重複している配列の高速ソートアルゴリズム？

Question

ほとんどの場合、複製された要素のセットが少ない配列を並べ替える効率的な方法はありますか？ことequalの順序を仮定

{10、10、55、10、999、8851243、10、55、55、55、10、999、8851243、10}

：すなわち、のようなリストであります要素は重要ではありませんが、良いワーストケース/平均ケースアルゴリズムは何ですか？

Answer 1

、最初に一度、配列を反復し、ハッシュテーブルを使用することができる（これは（N）ここで、n =リストのサイズOである）は、個々の要素の出現回数を数えます。次に、すべての固有の要素を取り、それらをソートします（これはk =ユニーク要素の数であるO（k log k）です）。これをO（n）ステップのn要素のリストに展開し、ハッシュ表。 k < < nなら、時間を節約できます。

Answer 2

IMO Pidgeonhole sortは、データのための良い例です。

私はちょっと分かります：配列のユニークな要素の量が妥当であり、重複がたくさんあることが分かっているなら、ソートのようなものを実装すると思いますが、 "バケット"動的。最初のパスの後、重複を取り除き、いくつかの良いソートアルゴリズムで重複しないで配列をソートし、ソートされた配列をカウントソートのように復元します。実際に

Answer 3

アルゴリズムは最適ではありませんが、単純です：
すべてをトライに入れて、葉をカウンターにすることができます。これはO（n * m）を取る必要があります。ここで、nは要素の数、mは最大要素のサイズです（通常は定数ですが、必ずしもそうではありません）。次に、先行注文はネクタイを横切り、葉を打ったときに現在のキーの要素counterを出力します。これは、O（n + p）だけを取る必要があります。ここで、pはトライのサイズです。これはnに比べて小さいはずです。

Answer 4

私はCounting sortにいくつかのマッピング機能を試してみます。つまり要素の範囲に等しい大きさの周波数配列を使用するのではなく、配列全体を繰り返し、異なる要素を書き留め、それらを周波数の配列へのマッピング関数で使用します。

この方法では、アルゴリズムには余分な繰り返しとマッピング機能しかありません。一定の時間（ハッシュテーブルの一部のキングを使用）で動作するはずです。この手法の複雑さは、O(n)であり、最適であるはずです。 Cで

Answer 5

実施++ハッシュテーブルの

• カウント周波数と店舗@Antti Huimaにより示唆されるようにアルゴに基づきます。
• ハッシュテーブルの要素を並べ替えます。

• 入力配列を周波数によってソートされた要素で上書きします。

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