Лучший алгоритм непрерывной сортировки?

Ответ 1

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

Кроме того, восстановление i-го элемента может быть выполнено путем аннотирования каждого ребра (или, что эквивалентно, node) в дереве с общим количеством узлов ниже него. Тогда можно найти i-й элемент в пространстве Θ (lg n) и Θ (1) с чем-то вроде:

node *find_index(node *root, int i) {
  while (node) {
    if (i == root->left_count)
      return root;
    else if (i < root->left_count)
      root = root->left;
    else {
      i -= root->left_count + 1;
      root = root->right;
    }
  }
  return NULL; // i > number of nodes
}

Реализация, которая поддерживает это, можно найти в debian libavl; к сожалению, сайт-разработчик кажется недоступным, но его можно найти из debian servers.

Ответ 2

Структура, которая используется для индексов программ баз данных, является деревом B+. Это сбалансированное древовидное дерево.

Из Википедии:

Для дерева B + B-порядка с h уровнями индекса:

• Максимальное количество сохраненных записей: n = b ^ h
• Минимальное количество ключей - 2 (b/2) ^ (h-1)
• Пространство, необходимое для хранения дерева, это O (n)
• Вставка записи требует операций O (log-b (n)) в худшем случае
• Для поиска записи требуются операции O (log-b (n)) в худшем случае
• Для удаления (ранее расположенной) записи требуются операции O (log-b (n)) в худшем случае
• Выполнение запроса диапазона с элементами k, входящими в диапазон, требует O (log-b (n + k)) операций в худшем случае.

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

Вы можете оптимизировать структуру своей программы, играя с b, размером с ведрами.

Интересная презентация о деревьях B +: Tree-Structured Indexes

Вы можете получить весь код на С++.

Изменить: теперь я вижу ваш комментарий, что ваше требование знать "i-й отсортированный элемент в наборе" является важным. Внезапно, что делает многие структуры данных менее оптимальными.

Вероятно, вам лучше всего выбрать SortedList или даже лучше, SortedDictionary. См. Статью: Сжатие большей производительности из SortedList. Обе структуры имеют функцию GetKey, которая возвращает i-й элемент.

Ответ 3

Вероятно, куча сортировки. Кучи - это только O (log N), чтобы добавить новые данные, и вы можете удалить результаты сети в в любое время в O (N log N) времени.

Если вам всегда нужен весь список, отсортированный каждый раз, тогда не так много других опций, кроме вставки сортировки. Вероятно, это будет O (N ^ 2), хотя с ОГРОМНЫМ хлопотом связанных списков пропуска вы можете сделать это O (N log N).

Ответ 4

Я бы использовал очередь кучи/приоритета. Худший случай такой же, как средний случай для времени выполнения. Следующий элемент можно найти в O (log n) времени.

Вот шаблонная реализация С#, которую я получил из this код.

Ответ 5

Хорошо, вы хотите отсортировать данные, но вам нужно извлечь их с помощью номера индекса.

Начните с базового дерева, такого как аплодированные деревья Красно-Черных.

Измените дерево-алгоритм таким образом, чтобы при вставке элементов в дерево все узлы, встречающиеся во время вставки и удаления, учитывали количество элементов под каждой ветвью.

Затем, когда вы извлекаете данные из дерева, вы можете рассчитать индекс по мере того, как вы идете, и знать, какая ветвь берется на основе того, больше или меньше индекса, который вы пытаетесь извлечь.

Еще одно соображение. Элементы 10M + в дереве, использующем динамическое распределение памяти, будут всасывать большие издержки памяти. т.е. указатели могут занимать больше места, чем ваши фактические данные, а также любой другой элемент, используемый для реализации структуры данных. Это приведет к серьезной фрагментации памяти, а в худших случаях ухудшит общую производительность системы. (Извлечение данных из виртуальной памяти.) Возможно, вы захотите рассмотреть возможность комбинирования блоков и динамической памяти. Что-то, где вы сортируете дерево в блоки данных, тем самым уменьшая объем памяти.

Ответ 6

Если вам просто нужно знать i-й наименьший элемент, как он говорит в комментариях, используйте алгоритм BFPRT, названный в честь последних имен авторов: Blum, Floyd, Pratt, Rivest и Tarjan, и, как правило, быть самой большой концентрацией крупных компьютерных наук в той же работе. O (n) в худшем случае.

Ответ 7

Ознакомьтесь с comparison алгоритмов сортировки в Википедии.

Ответ 8

Рандомизированные Jumplists также интересны. Они требуют меньше места как BST и skiplists. Вставка и удаление - O (log n)

Ответ 9

Посредством "набора двойных данных" вы имеете в виду набор действительных чисел? Один из наиболее часто используемых алгоритмов для этого - куча сортировки, я бы это выяснил. Большая часть его операций - O (n * log (n)), что довольно хорошо, но не соответствует всем вашим критериям. Преимущества heapsort в том, что он достаточно прост для самокодирования, и многие языки предоставляют библиотеки для управления отсортированной кучей.