Быстрые алгоритмы сортировки для массивов с в основном дублированными элементами? - PullRequest
Новая
       29

Быстрые алгоритмы сортировки для массивов с в основном дублированными элементами?

11 голосов
/ 18 ноября 2011

Каковы эффективные способы сортировки массивов, которые имеют в основном небольшой набор дублированных элементов?То есть список вроде:

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

Предполагая, чтопорядок элементов equal не имеет значения, каковы хорошие алгоритмы наихудшего / среднего случая?

Ответы [ 5 ]

16 голосов
/ 18 ноября 2011

На практике вы можете сначала выполнить итерацию по массиву один раз и использовать хеш-таблицу для подсчета количества вхождений отдельных элементов (это O (n), где n = размер списка).Затем возьмите все уникальные элементы и отсортируйте их (это O (k log k), где k = количество уникальных элементов), а затем разверните это обратно к списку из n элементов за O (n) шагов, восстанавливая счетчики изхеш-таблица.Если k << n, вы экономите время. </p>

4 голосов
/ 18 ноября 2011

Я бы попробовал Подсчет сортировки с некоторой функцией отображения. То есть. вы не будете использовать массив частот размером, равным диапазону элементов, вместо этого вы будете выполнять итерацию по массиву, записывать отдельные элементы и использовать их в функции отображения в массив частот.

Таким образом, алгоритм имеет только одну дополнительную итерацию и функцию отображения, которая должна работать в постоянное время (с использованием некоторой хеш-таблицы). Сложность этого подхода будет O(n), что должно быть оптимальным.

2 голосов
/ 18 ноября 2011

Не самый лучший алгоритм, но простой:
Вы можете положить все в дерево, и листья будут счетчиками. Это должно занять O (n * m), где n - количество элементов, а m - размер самого большого элемента (обычно это будет константа, но не обязательно). Затем предварительный заказ пересекает связь, выводя counter элементов текущего ключа, когда вы нажимаете на лист. Это должно занять только O (n + p), где p - размер дерева, который должен быть крошечным по сравнению с n.

1 голос
/ 08 августа 2016

Реализация в C ++ на основе алгоритма, предложенного @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;
  }
}
0 голосов
/ 18 ноября 2011

IMO Сорт Pidgeonhole является хорошим примером для таких данных.

Я поясню немного: если вы знаете, что количество уникальных элементов в массиве является разумным, и вы знаете, что есть много дубликатов, я бы подумал о реализации чего-то вроде сортировки с подсчетом, но сделать список "сегментов" динамическим , После первого прохода вы избавитесь от дубликатов, затем отсортируете массив без дубликатов с помощью хорошего алгоритма сортировки, а затем восстанавливаете отсортированный массив так, как это делает счетная сортировка.

...