Алгоритм анализа предварительной сортировки?

Question

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

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

Answer 1

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

Самоанализ это довольно захватывающе, поскольку это позволяет полностью избежать квадратичного наихудшего случая быстрой сортировки.Вместо вашего естественного вопроса "как мне определить, что данные почти отсортированы", он фактически спрашивает себя по ходу работы: "не слишком ли это долго?".Если ответ положительный, он переключается с быстрой сортировки на кучную.

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

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

Answer 2

Существует также 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), и у него отличные свойства "локальности".

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

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

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