Эффективный алгоритм сортировки для почти отсортированного списка, содержащего данные о времени?

Question

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

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

Учитывая эти условия, может ли кто-нибудь предложить алгоритм, который стоит рассмотреть в дополнение к сортировке вставки? Кроме того, как определить «в основном отсортированный», чтобы решить, что такое хороший способ сортировки? Что я имею в виду, так это то, как я просматриваю свои данные и решил: «Это не так, как я думал, это, может быть, сортировка вставки больше не лучший вариант»? Будет оценена любая ссылка на статью, в которой рассматривается сложность процесса, которая лучше определяет сложность по отношению к данным степени.

Благодаря

Edit: спасибо всем за вашу информацию. На данный момент я собираюсь с простой вставкой или слиянием (в зависимости от того, что я уже написал ранее). Тем не менее, я буду пытаться использовать некоторые другие методы, когда-то ближе к фазе оптимизации (поскольку они прикладывают больше усилий для реализации). Я благодарен за помощь

Answer 1

Вы можете принять предложенный вариант (2) - сортировать данные во время вставки элементов.

Используйте skip list, отсортированные по времени, по возрастанию для хранения ваших данных.

• После того, как новый вхож прибывает - проверить, если он больше, то последний элемент (легко и быстро), если это - просто добавить его (это легко сделать в списке пропуска). В этом случае в списке пропусков необходимо будет добавить в среднем 2 узла в среднем для этих случаев и будет O(1) на в среднем для этих случаев.
• Если элемент не больше, то последний элемент - добавьте его в список пропуска в качестве стандартной вставки op, которая будет O(logn).

Этот подход даст вам O(n+klogn) алгоритм, где k - количество вставленных элементов.

Answer 2

Я бы выбрал merge sort, если вы реализуете натуральную версию, вы получите лучший случай O(N) с типичным и худшим случаем O(N log N), если у вас возникнут проблемы. Вставка вы получаете в худшем случае O(N^2) и лучший случай O(N).

Answer 3

Существует множество адаптивных алгоритмов сортировки, которые специально предназначены для сортировки в основном отсортированных данных. Игнорируя тот факт, что вы храните даты, вы можете посмотреть на smoothsort или декартово дерево сортировки как алгоритмы, которые могут сортировать данные, которые разумно отсортированы в наихудшем случае O (n log n) и наилучшем случае O (n) время. Преимущество Smoothsort состоит в том, что требуется только O (1) пространство, например сортировка вставки.

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

Надеюсь, это поможет!

Answer 4

Если ваша библиотека ОС или C предоставляет функцию слияния, очень вероятно, что она уже обрабатывает случай, когда указанные данные частично упорядочены (в любом направлении), выполняемые в O (N) времени.

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

Answer 5

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

Answer 6

Вы можете отсортировать список n с k Элементы не на месте в O(n + k lg k) раз.

См: http://www.quora.com/How-can-I-quickly-sort-an-array-of-elements-that-is-already-sorted-except-for-a-small-number-of-elements-say-up-to-1-4-of-the-total-whose-positions-are-known/answer/Mark-Gordon-6?share=1

Основная идея заключается в следующем:

• Итерация по элементам массива, строящих возрастающую подпоследовательность (если текущий элемент больше или равен последнему элементу подпоследовательность, добавьте его в конец подпоследовательности. В противном случае отбросьте как текущий элемент, так и последний элемент подпоследовательности). Это занимает O(n) раз.
• Вы отбросите не более 2k элементов с k Элементы неуместны.
• Сортировка 2k элементов, которые были отброшены с использованием алгоритма сортировки O(k lg k), такого как сортировка слияния или heapsort.
• Теперь у вас есть два отсортированных списка. Объедините списки в O(n), как и на этапе слияния сортировки слияния.

Общая Трудоемкость = O(n + k lg k)

Общая пространство сложность = O(n)

(это может быть изменено, чтобы запустить в O(1) пространства, если вы можете объединить в O(1) пространства, но это ни в коем случае не тривиально)