Какой алгоритм сортировки работает лучше всего над главным образом отсортированными данными? [закрытый]

168
задан gsamaras 10 October 2015 в 14:37
поделиться

14 ответов

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

254
ответ дан Dominic Rodger 23 November 2019 в 20:53
поделиться

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

-1
ответ дан Werg38 23 November 2019 в 20:53
поделиться

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

0
ответ дан Brian 23 November 2019 в 20:53
поделиться

обдумывают "куча" Попытки. Я полагаю, что это является самым последовательным из O (n LG n) виды.

0
ответ дан Paul Nathan 23 November 2019 в 20:53
поделиться

Вид вставки является лучшим случаем O (n) на отсортированном входе. И это очень близко на главным образом отсортированном входе (лучше, чем быстрая сортировка).

0
ответ дан jjnguy 23 November 2019 в 20:53
поделиться

Если Вы нуждаетесь в определенной реализации для сортировки алгоритмов, структур данных или чего-нибудь, что имеет ссылку на вышеупомянутое, я мог рекомендовать Вам превосходное "Структуры данных и Алгоритмы" проект на CodePlex?

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

Просто моя небольшая мелкая частица соли.

1
ответ дан Maxime Rouiller 23 November 2019 в 20:53
поделиться

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

Позволяют N быть количеством общего количества объектов, M быть числом не в порядке.

Пузырьковая сортировка должна будет сделать, что-то как 2*M+1 проходит через все объекты N. Если M является очень маленьким (0, 1, 2?), я думаю, что это будет очень трудно разбить.

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

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

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

Дальнейшие размышления (в течение ночи): Если M+1 < N/M, тогда можно просканировать список, ища выполнение N/M подряд, которые отсортированы, и затем разворачивают то выполнение в любом направлении для нахождения неисправных объектов. Это возьмет самое большее сравнения на 2 Н. Можно тогда отсортировать неотсортированные объекты и сделать отсортированное слияние в двух списках. Общие сравнения должны меньше, чем что-то как 4N+M log2 (M), который собирается разбить любую неспециализированную программу сортировки, я думаю. (Еще больше мысль: это более хитро, чем я думал, но я все еще думаю, что это довольно возможно.)

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

2
ответ дан Sol 23 November 2019 в 20:53
поделиться

Как все остальные сказали, остерегаться наивного Quicksort - который может иметь O (N^2) производительность на отсортированных или почти отсортированных данных. Тем не менее, с соответствующим алгоритмом для выбора центра (или случайный или median-three - видят Выбор Pivot for Quicksort ), Quicksort будет все еще работать нормально.

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

2
ответ дан Community 23 November 2019 в 20:53
поделиться

вставка или вид оболочки!

5
ответ дан ninesided 23 November 2019 в 20:53
поделиться

Splaysort является неясным методом сортировки на основе косые деревья , тип адаптивного двоичного дерева. Splaysort хорош не только для частично отсортированных данных, но также и частично отсортированных по реверсу данных, или действительно любых данных, которые имеют любой вид существующего ранее порядка. Это - O (nlogn) в общем случае и O (n) в случае, где данные отсортированы в некотором роде (вперед, реверс, канал органа, и т.д.).

Его большое преимущество перед видом вставки состоит в том, что он не возвращается к O (n^2) поведение, когда данные не отсортированы вообще, таким образом, Вы не должны быть абсолютно уверены, что данные частично отсортированы перед использованием его.

Его недостаток является дополнительным пространством наверху косой древовидной структуры, в которой оно нуждается, а также время, требуемое создавать и уничтожать косое дерево. Но в зависимости от размера данных и суммы pre-sortedness, который Вы ожидаете, издержки могут стоить того для увеличения скорости.

А работа на splaysort была опубликована в программном обеспечении - Практика & Опыт.

7
ответ дан TimB 23 November 2019 в 20:53
поделиться

Попробуйте самосозерцательный вид. http://en.wikipedia.org/wiki/Introsort

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

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

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

, Если Вы - проверка программиста на C++ Ваш станд.:: алгоритм сортировки. Это может уже использовать самосозерцательный вид внутренне.

11
ответ дан Nils Pipenbrinck 23 November 2019 в 20:53
поделиться

Вид вставки со следующим поведением:

  1. Для каждого элемента k в слотах 1..n, сначала проверьте ли el[k] >= el[k-1]. Если так, перейдите к следующему элементу. (Очевидно, пропустите первый элемент.)
  2. В противном случае двоичный поиск использования в элементах 1..k-1 для определения местоположения вставки затем бегите стремглав элементы. (Вы могли бы сделать это, только если k>T, где T некоторое пороговое значение; с маленьким k это - излишество.)

Этот метод делает наименьшее количество количества сравнений.

19
ответ дан Jason Cohen 23 November 2019 в 20:53
поделиться

timsort

Timsort является "адаптивной, стабильной, естественной сортировкой с объединением" с" сверхъестественная производительность на многих видах частично заказанных массивов (меньше, чем LG (N!) сравнения, необходимые, и только N-1)". Python, встроенный sort(), использовал этот алгоритм в течение некоторого времени, по-видимому, с хорошими результатами. Это специально предназначено, чтобы обнаружить и использовать в своих интересах частично отсортированные подпоследовательности во входе, которые часто происходят в реальных наборах данных. Часто имеет место в реальном мире, что сравнения являются намного более дорогими, чем свопинг объектов в списке, так как каждый обычно просто подкачивает указатели, который очень часто делает timsort отличным выбором. Однако, если Вы знаете, что Ваши сравнения являются всегда очень дешевыми (запись игрушечной программы для сортировки 32-разрядных целых чисел, например), другие алгоритмы существуют, которые, вероятно, будут работать лучше. Самый легкий способ использовать в своих интересах timsort состоит в том, чтобы, конечно, использовать Python, но так как Python является открытым исходным кодом, Вы могли бы также быть в состоянии одолжить код. Поочередно, описание выше содержит более чем достаточно детали для записи собственной реализации.

30
ответ дан zaphod 23 November 2019 в 20:53
поделиться

Сортировка вставкой занимает время O (n + количество инверсий).

Инверсия - это пара ( i, j) такие, что i a [j] . То есть пара не по порядку.

Одним из показателей «почти отсортированности» является количество инверсий - можно взять «почти отсортированные данные» означать данные с небольшим количеством инверсий. Если известно, что количество инверсий должно быть линейным (например, вы только что добавили O (1) элементов в отсортированный список), сортировка вставкой занимает время O (n).

3
ответ дан 23 November 2019 в 20:53
поделиться
Другие вопросы по тегам:

Похожие вопросы: