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

Question

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

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

Answer 1

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

Introsort довольно захватывающе, так как он полностью избегает квадратичного наихудшего случая быстрой сортировки. Вместо вашего естественного вопроса «как я могу определить, что данные почти отсортированы», он фактически задает себе вопрос: «Это занимает слишком много времени?». Если ответ «да», он переключается с быстрой сортировки на heapsort.

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

Answer 5

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

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

Answer 6

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

Answer 7

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

Answer 8

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