Как эффективно сортировать массив упорядоченных последовательностей

Question

Я реализую сложный алгоритм, частью которого является сортировка массива упорядоченных последовательностей чисел.Весь алгоритм должен быть nlog (n) сложность , поэтому эта часть должна быть такой же или лучше, но я не знаю, как это сделать.

Есть пример.Существует массив последовательностей:

(0)
(0,1)
(0)
(0,5)
(2,4)
()
(0,5)
()
(2,4)
(1,3,4)

, а окончательная сортировка должна быть:

()
()
(0)
(0)
(0,1)
(0,5)
(0,5)
(1,3,4)
(2,4)
(2,4)

Есть несколько важных замечаний:

• сортировка лексикографическая
• последовательности упорядочены, но нет гарантии непрерывности
• есть также пустые последовательности
• есть много идентичных последовательностей
• последовательности от 0 додлиной в сотни, не более
• массив может быть длиной 100 КБ, вероятно, не более
• Окончательная реализация будет в C ++, но теперь это, вероятно, не важно

МожетВы предлагаете мне лучший способ, как отсортировать это, пожалуйста?Большое спасибо

Answer 1

Ваша проблема похожа на radix sort, в этом случае сначала отсортируйте последовательности по крайнему правому элементу (например, 100-му элементу), если такого элемента не существует, установите его как min possible value - 1 (например, вв этом случае я вижу -1), затем сортируем эту отсортированную последовательность со вторым правым элементом и продолжаем таким образом.

Также, если все элементы в последовательностях находятся между 1..k (в этом случае я могу видеть таммежду 1..9) используйте counting sort, чтобы отсортировать их в O (n), если вы можете использовать сортировку при подсчете, время сортировки равно O (n), но в противном случае время сортировки равно O (n).журнал n).

Answer 2

Если вы используете быструю сортировку, то алгоритм сортировки будет O (n log n). То, как вы должны сравнивать эти два элемента, не имеет отношения к сложности самой сортировки и имеет свою собственную сложность (предположительно O (m)).

Answer 3

Если вы можете интегрировать код GPLv3 в свой проект, GNU Sort может быть хорошим началом По крайней мере, когда я запустил его на вашем вводе сэмпла, я получил ваш вывод сэмпла, так что это не сразу неправильно.