Предварительная сортировка аналитического алгоритма?

Также есть SmoothSort, который, по-видимому, довольно сложно реализовать, но он варьируется от O (N log N) до O (N) в зависимости от того, как отсортированы данные в начале.

http://en.wikipedia.org/wiki/Smoothsort

Длинный сложный PDF-файл: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

Однако, если ваши данные действительно огромны и вам нужно обращаться к ним последовательно, лучше всего подходит сортировка слиянием. Это всегда O (N log N), и у него отличные свойства «локальности».

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

Одно из возможных решений - взять первый, последний и средний элемент в текущем диапазоне сортировки (во время операции QuickSort) и выбрать средний в качестве поворотного элемента.

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

QuickSort создает проблему только тогда, когда набор данных огромен и уже в основном отсортирован, я бы использовал следующую эвристику (в ожидании полномасштабного решения):

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

• Если у вас есть быстрый (индексированный) доступ к записям (элементам), возьмите выборку с 1 записью в каждых N записях и посмотрите, отсортированы ли они уже. Должно быть достаточно быстрым для небольшой выборки, и тогда вы сможете решить, использовать ли быструю сортировку или нет.

Вы бы по-прежнему необходимо просмотреть все записи, чтобы определить, отсортированы они или нет, поэтому для повышения производительности начните с первой записи и выполняйте остальные, пока не заметите, что что-то не отсортировано должным образом, или не дойдете до конца списка. Если вы обнаружите промах, то отсортируйте элементы только от этой позиции до конца (так как начало списка уже отсортировано).

В каждом пункте второй части посмотрите, является ли элемент <чем последний элемент в первой части, и если да, используйте сортировку вставкой ТОЛЬКО в первую часть. В противном случае быстрая сортировка по всем остальным элементам второй части. Таким образом, сортировка оптимизируется для конкретного случая.

Чтобы показать концептуальную мысль, которую люди еще не сделали: Quicksort - это здравый алгоритм «разделяй и властвуй» с очевидной ошибкой в ​​редких случаях. Предположим, вы хотите отсортировать стопку студенческих работ. (Что я имею дело с некоторой регулярностью.) В алгоритме быстрой сортировки вы выбираете бумагу, точку опоры. Затем разделите остальные листы в зависимости от того, находятся ли они до или после поворота. Затем повторите то же самое с двумя вложенными стопками. Что за ошибка? Поворотным элементом может быть имя, которое находится ближе к одному концу списка, а не в середине, так что разделение его на две стопки не дает многого.

Сортировка слиянием - это еще один работающий алгоритм «разделяй и властвуй» в другом порядке. Вы можете объединить два отсортированных списка за линейное время. Разделите листы на две равные или почти равные стопки, затем рекурсивно отсортируйте каждый, затем объедините. Сортировка слиянием не содержит ошибок. Одна из причин того, что быстрая сортировка более популярна, чем сортировка слиянием, - историческая: быстрая сортировка (обычно) и работает без дополнительной памяти. Но в наши дни сохранение сравнений может быть более важным, чем сохранение памяти, и реальная перестановка часто абстрагируется путем перестановки указателей. Если бы все было так всегда, то я подозреваю, что сортировка слиянием была бы более популярной, чем быстрая сортировка. (И, возможно, добавление «быстро» к имени было хорошим торговым умением.)

и реальная перестановка часто абстрагируется перестановкой указателей. Если бы все было так всегда, то я подозреваю, что сортировка слиянием была бы более популярной, чем быстрая сортировка. (И, возможно, добавление «быстро» к имени было хорошим торговым умением.)

и реальная перестановка часто абстрагируется перестановкой указателей. Если бы все было так всегда, то я подозреваю, что сортировка слиянием была бы более популярной, чем быстрая сортировка. (И, возможно, добавление слова «быстро» к названию было хорошим умением продавать.)