Вид пузыря ужасен. Это всегда O (n ^ 2). По крайней мере, убери это из своего ответа, чтобы оно было правильным, пожалуйста.
Jjnguy
79
jjnguy, это просто неправильно. Я думаю, что вам нужно повторно принять ваш класс алгоритмов. На почти отсортированных данных (это адаптивный случай) это O (N). Однако для данных требуется 2 прохода, а для вставки - только 1 для почти отсортированных данных, что делает вставку победителем. Пузырь все еще хорош, хотя
mmcdole
3
Производительность действительно сильно ухудшается, если ваши данные почти не отсортированы. Я бы все равно не использовал это, лично.
Blorgbeard выходит
5
Эта ссылка была сломана, когда я попробовал. Попробуйте вместо этого: sorting-algorithms.com
Майкл Ла Вой
107
Только несколько предметов => сортировка по вставке
Элементы в основном уже отсортированы => сортировка по вставке
Обеспокоены наихудшими сценариями => HEAP SORT
Интересует хороший результат в среднем случае => QUICKSORT
Предметы взяты из плотной вселенной => ВЕДРО СОРТИРОВАТЬ
Желание написать как можно меньше кода => SOR INSERTION
Это именно тот ответ, который я искал, я читаю книги, но я не вижу четкого объяснения выбора алгоритмов в конкретных случаях. Не могли бы вы уточнить это или передать ссылку, чтобы я мог выследить это еще немного? Спасибо
Симран Каур
9
Вы должны добавить «Данные уже отсортированы по другому критерию => MERGE SORT»
Джим Хунзикер
30
timsort
Timsort - это «адаптивная, стабильная, естественная сортировка» с « сверхъестественными характеристиками во многих видах частично упорядоченных массивов (требуется меньше чем lg (N!) Сравнений и всего лишь N-1)». Python встроенныйsort()использовал этот алгоритм в течение некоторого времени, по-видимому, с хорошими результатами. Он специально разработан для обнаружения и использования частично отсортированных подпоследовательностей во входных данных, которые часто встречаются в реальных наборах данных. В реальном мире часто бывает так, что сравнения намного дороже, чем обмен элементами в списке, поскольку обычно просто меняются указатели, что очень часто делает timsort отличным выбором. Однако, если вы знаете, что ваши сравнения всегда очень дешевы (например, пишите игрушечную программу для сортировки 32-разрядных целых чисел), существуют другие алгоритмы, которые, вероятно, будут работать лучше. Конечно, самый простой способ воспользоваться преимуществами timsort - это использовать Python, но, поскольку Python является открытым исходным кодом, вы также можете позаимствовать код. Альтернативно, приведенное выше описание содержит более чем достаточно подробностей, чтобы написать собственную реализацию.
@JF Себастьян: timsort намного быстрее, чем lg(n!)сравнения в почти отсортированном массиве, вплоть до O(n)! | @behrooz: Нет сравнение сортировка может иметь средний случай лучше O(n log n), и lg(n!)это O(n log n). Так что худший случай тимсорта асимптотически не хуже, чем у любого другого вида сравнения. Кроме того, его лучший случай лучше или равен любому другому виду сравнения.
Артелиус
3
Timsort все еще O (nlogn) в худшем случае, но его хорошие случаи довольно приятны. Вот сравнение с некоторыми графиками: stromberg.dnsalias.org/~strombrg/sort-comparison Обратите внимание, что timsort в Cython был не так быстр, как Python, встроенный в timsort в C.
user1277476
19
Вставка сортируется со следующим поведением:
Для каждого элемента kв слотах 1..nсначала проверьте, есть ли el[k] >= el[k-1]. Если это так, перейдите к следующему элементу. (Очевидно, пропустить первый элемент.)
Если нет, используйте бинарный поиск в элементах, 1..k-1чтобы определить местоположение вставки, затем переместите элементы поверх. (Вы можете сделать это, только если k>Tгде-то Tесть какое-то пороговое значение; с небольшим kэто перебор.)
Этот метод делает наименьшее количество сравнений.
Я думаю, что пузырьковая сортировка может побить это, если количество несортированных элементов очень мало (например, один или два), но в целом это кажется мне лучшим решением.
Соль
Благодаря шагу 1 для любых уже отсортированных элементов существует ровно одно сравнение и ноль перемещений данных, что, очевидно, является лучшим, что вы можете сделать. Шаг 2 - это тот, который вы могли бы улучшить, но пузырь переместит то же количество элементов и может иметь больше сравнений, в зависимости от вашего значения.
Джейсон Коэн
На самом деле, если подумать, я думаю, что пузырьковая сортировка сильнее, чем я думала. Это на самом деле довольно сложный вопрос. Например, если вы берете случай, когда список полностью отсортирован, за исключением того, что элемент, который должен быть последним, стоит первым, сортировка по пузырькам значительно превзойдет то, что вы описываете.
Соль
Я попытался реализовать это, но бинарный поиск не сильно улучшился, так как вам все еще нужно переместить весь блок, чтобы вставить элемент. Таким образом, вместо 2xrange вы получаете range + logb (range).
Он основан на быстрой сортировке, но позволяет избежать наихудшего поведения, которое имеет быстрая сортировка для почти отсортированных списков.
Хитрость в том, что этот алгоритм сортировки обнаруживает случаи, когда быстрая сортировка переходит в режим наихудшего случая и переключается на сортировку с кучей или слиянием. Почти отсортированные разделы обнаруживаются с помощью некоторого не наивного метода разделов, а небольшие разделы обрабатываются с помощью сортировки вставками.
Вы получаете лучшие из всех основных алгоритмов сортировки за счет увеличения кода и сложности. И вы можете быть уверены, что никогда не столкнетесь с наихудшим поведением, независимо от того, как выглядят ваши данные.
Если вы программист на C ++, проверьте алгоритм std :: sort. Возможно, он уже использует внутреннюю сортировку.
Splaysort - это неясный метод сортировки, основанный на деревьях сплайнов , тип адаптивного двоичного дерева. Splaysort хорош не только для частично отсортированных данных, но также для частично отсортированных данных или любых данных, которые имеют какой-либо ранее существовавший порядок. Это O (nlogn) в общем случае и O (n) в случае, когда данные сортируются каким-либо образом (вперед, назад, труба органа и т. Д.).
Его большое преимущество перед сортировкой вставок состоит в том, что она не возвращается к поведению O (n ^ 2), когда данные вообще не сортируются, поэтому вам не нужно быть абсолютно уверенным, что данные частично сортируются перед их использованием. ,
Его недостатком является дополнительное пространство, необходимое для структуры Splay Tree, а также время, необходимое для создания и уничтожения Splay Tree. Но в зависимости от ожидаемого размера данных и объема предварительной сортировки, издержки могут стоить увеличения скорости.
Сглаживание Дейкстры отлично подходит для уже отсортированных данных. Это вариант heapsort, который работает в O (n lg n) наихудшем случае и O (n) в лучшем случае. Я написал анализ алгоритма, если вам интересно, как он работает.
Натуральная сортировка слиянием - еще один действительно хороший вариант для этого - это вариант сортировки снизу вверх, который работает, обрабатывая входные данные как конкатенацию нескольких различных отсортированных диапазонов, а затем используя алгоритм слияния для объединения их вместе. Вы повторяете этот процесс, пока весь входной диапазон не будет отсортирован. Это выполняется за O (n), если данные уже отсортированы, и O (n lg n) в худшем случае. Это очень элегантно, хотя на практике это не так хорошо, как некоторые другие адаптивные сорта, такие как Timsort или smoothsort.
Каковы константы времени сглаживания по сравнению с другими алгоритмами сортировки? (т.е. время выполнения (сглаживание) / время выполнения (вставка-сортировка) для тех же данных)
Арне Бабенхаузерхайде
4
Если элементы уже отсортированы или имеется только несколько элементов, это был бы идеальный вариант использования Insertion Sort!
Сортировка вставки занимает время O (n + количество инверсий).
Инверсия - это пара (i, j)такая, что i < j && a[i] > a[j]. То есть пара не в порядке.
Одной из мер «почти отсортированных» является количество инверсий - можно считать «почти отсортированные данные» для обозначения данных с небольшим количеством инверсий. Если известно, что число инверсий является линейным (например, вы только что добавили O (1) элементов в отсортированный список), сортировка вставкой занимает O (n) времени.
Как и все остальные, будьте осторожны с наивной быстрой сортировкой - она может иметь производительность O (N ^ 2) для отсортированных или почти отсортированных данных. Тем не менее, с помощью соответствующего алгоритма для выбора оси (либо случайным или срединного троих - см Выбор Pivot для Quicksort ), Quicksort будет по- прежнему работать здраво.
В общем, сложность выбора таких алгоритмов, как сортировка вставки, заключается в том, чтобы решить, когда данные достаточно не в порядке, чтобы Quicksort действительно был быстрее.
Я не собираюсь притворяться, что у меня есть все ответы здесь, потому что я думаю, что получение реальных ответов может потребовать кодирования алгоритмов и профилирования их по репрезентативным выборкам данных. Но я думал об этом вопросе весь вечер, и вот что мне пришло в голову до сих пор, и некоторые предположения о том, что работает лучше всего, где.
Пусть N будет общее количество элементов, M будет количество не в порядке.
Bubble sort должен сделать что-то вроде 2 * M + 1 проходов через все N предметов. Если М очень мало (0, 1, 2?), Я думаю, что это будет очень трудно победить.
Если M мало (скажем, меньше, чем log N), сортировка вставок будет иметь среднюю производительность. Тем не менее, если не будет хитрости, у меня будет очень плохая производительность в худшем случае. (Правильно? Если последний элемент в порядке идет первым, то, насколько я вижу, вам нужно вставить каждый отдельный элемент, что снизит производительность.) Я предполагаю, что для этого существует более надежный алгоритм сортировки. дело, но я не знаю, что это.
Если M больше (скажем, равно или больше, чем log N), интроспективная сортировка почти наверняка лучше.
Исключение из всего этого: если вы действительно заранее знаете, какие элементы не отсортированы, тогда вам лучше всего выбрать эти элементы, отсортировать их с помощью интроспективной сортировки и объединить два отсортированных списка в один отсортированный список. Если бы вы могли быстро выяснить, какие предметы вышли из строя, это также было бы хорошим общим решением, но я не смог найти простой способ сделать это.
Дальнейшие размышления (в одночасье): если M + 1 <N / M, то вы можете отсканировать список в поисках серии N / M в отсортированной строке, а затем развернуть этот прогон в любом направлении, чтобы найти выход из заказ товаров. Это займет не более 2N сравнений. Затем вы можете отсортировать несортированные элементы и выполнить сортировку по двум спискам. Полное сравнение должно быть меньше чем что-то вроде 4N + M log2 (M), что, я думаю, превзойдет любую неспецифическую процедуру сортировки. (Даже дальше подумал: это сложнее, чем я думал, но я все еще думаю, что это вполне возможно.)
Другая интерпретация вопроса заключается в том, что может быть много неупорядоченных элементов, но они очень близки к тому, где они должны быть в списке. (Представьте, что вы начинаете с отсортированного списка и меняете каждый другой элемент на тот, который следует за ним.) В этом случае я думаю, что сортировка пузырьков работает очень хорошо - я думаю, что число проходов будет пропорционально самому удаленному элементу. является. Сортировка вставки будет работать плохо, потому что каждый элемент не по порядку будет запускать вставку. Я подозреваю, что интроспективная сортировка или что-то подобное тоже будет хорошо работать.
Если вам нужна конкретная реализация для сортировки алгоритмов, структур данных или чего-либо, что имеет ссылку на вышеперечисленное, могу ли я порекомендовать вам отличный проект «Структуры данных и алгоритмы» на CodePlex?
В нем будет все необходимое, не изобретая велосипед.
Эта хорошая коллекция алгоритмов сортировки для этой цели в ответах, кажется, не хватает сортировка Gnome , которая также подойдет и, вероятно, потребует минимальных усилий по реализации.
Сортировка вставки - лучший вариант O (n) для отсортированного ввода. И это очень близко по большей части отсортированного ввода (лучше, чем быстрая сортировка).
Согласованность здесь не важна. Heapsort выдаст O (n lg n) даже на отсортированные данные и не очень адаптивен. Возможными вариантами могут быть: сортировка вставками, Timsort и Bubblesort.
Макс.
0
Bubble-sort (или, что еще безопаснее, двунаправленная пузырьковая сортировка), вероятно, идеально подходит для в основном отсортированных списков, хотя я держу пари, что измененная гребенная сортировка (с гораздо меньшим начальным размером разрыва) будет немного быстрее, когда список не будет ' Точно так же отлично отсортировано. Сортировка расчески ухудшается до сортировки пузыря.
ну, это зависит от варианта использования. Если вы знаете, какие элементы изменены, удаление и вставка будут наилучшим вариантом, насколько мне известно.
Этот «насколько мне известно» тест эффективности алгоритма скрасил мой день :) Однако, будучи серьезным, когда писал «удалить и вставить», вы имели в виду сортировку вставкой (которая уже упоминалась в предыдущих ответах) или предлагаете новый вид алгоритма? Если это так, пожалуйста, расширьте свой ответ.
yoniLavi
0
Сортировка пузырьков - определенно победитель. Следующим на радаре будет сортировка вставок.
Я бы посоветовал вам посмотреть доступные ответы перед публикацией, чтобы избежать дубликатов.
Angainor
-1
Держитесь подальше от быстрой сортировки - она очень неэффективна для предварительно отсортированных данных. Сортировка вставками хорошо обрабатывает почти отсортированные данные, перемещая как можно меньше значений.
Ответы:
Основываясь на научном методе просмотра анимированных GIF-файлов, я бы сказал, что Insertion и Bubble являются хорошими кандидатами.
источник
Только несколько предметов => сортировка по вставке
Элементы в основном уже отсортированы => сортировка по вставке
Обеспокоены наихудшими сценариями => HEAP SORT
Интересует хороший результат в среднем случае => QUICKSORT
Предметы взяты из плотной вселенной => ВЕДРО СОРТИРОВАТЬ
Желание написать как можно меньше кода => SOR INSERTION
источник
timsort
Timsort - это «адаптивная, стабильная, естественная сортировка» с « сверхъестественными характеристиками во многих видах частично упорядоченных массивов (требуется меньше чем lg (N!) Сравнений и всего лишь N-1)». Python встроенный
sort()использовал этот алгоритм в течение некоторого времени, по-видимому, с хорошими результатами. Он специально разработан для обнаружения и использования частично отсортированных подпоследовательностей во входных данных, которые часто встречаются в реальных наборах данных. В реальном мире часто бывает так, что сравнения намного дороже, чем обмен элементами в списке, поскольку обычно просто меняются указатели, что очень часто делает timsort отличным выбором. Однако, если вы знаете, что ваши сравнения всегда очень дешевы (например, пишите игрушечную программу для сортировки 32-разрядных целых чисел), существуют другие алгоритмы, которые, вероятно, будут работать лучше. Конечно, самый простой способ воспользоваться преимуществами timsort - это использовать Python, но, поскольку Python является открытым исходным кодом, вы также можете позаимствовать код. Альтернативно, приведенное выше описание содержит более чем достаточно подробностей, чтобы написать собственную реализацию.источник
lg(n!)сравнения в почти отсортированном массиве, вплоть доO(n)! | @behrooz: Нет сравнение сортировка может иметь средний случай лучшеO(n log n), иlg(n!)этоO(n log n). Так что худший случай тимсорта асимптотически не хуже, чем у любого другого вида сравнения. Кроме того, его лучший случай лучше или равен любому другому виду сравнения.Вставка сортируется со следующим поведением:
kв слотах1..nсначала проверьте, есть лиel[k] >= el[k-1]. Если это так, перейдите к следующему элементу. (Очевидно, пропустить первый элемент.)1..k-1чтобы определить местоположение вставки, затем переместите элементы поверх. (Вы можете сделать это, только еслиk>Tгде-тоTесть какое-то пороговое значение; с небольшимkэто перебор.)Этот метод делает наименьшее количество сравнений.
источник
Попробуйте интроспективную сортировку. http://en.wikipedia.org/wiki/Introsort
Он основан на быстрой сортировке, но позволяет избежать наихудшего поведения, которое имеет быстрая сортировка для почти отсортированных списков.
Хитрость в том, что этот алгоритм сортировки обнаруживает случаи, когда быстрая сортировка переходит в режим наихудшего случая и переключается на сортировку с кучей или слиянием. Почти отсортированные разделы обнаруживаются с помощью некоторого не наивного метода разделов, а небольшие разделы обрабатываются с помощью сортировки вставками.
Вы получаете лучшие из всех основных алгоритмов сортировки за счет увеличения кода и сложности. И вы можете быть уверены, что никогда не столкнетесь с наихудшим поведением, независимо от того, как выглядят ваши данные.
Если вы программист на C ++, проверьте алгоритм std :: sort. Возможно, он уже использует внутреннюю сортировку.
источник
Splaysort - это неясный метод сортировки, основанный на деревьях сплайнов , тип адаптивного двоичного дерева. Splaysort хорош не только для частично отсортированных данных, но также для частично отсортированных данных или любых данных, которые имеют какой-либо ранее существовавший порядок. Это O (nlogn) в общем случае и O (n) в случае, когда данные сортируются каким-либо образом (вперед, назад, труба органа и т. Д.).
Его большое преимущество перед сортировкой вставок состоит в том, что она не возвращается к поведению O (n ^ 2), когда данные вообще не сортируются, поэтому вам не нужно быть абсолютно уверенным, что данные частично сортируются перед их использованием. ,
Его недостатком является дополнительное пространство, необходимое для структуры Splay Tree, а также время, необходимое для создания и уничтожения Splay Tree. Но в зависимости от ожидаемого размера данных и объема предварительной сортировки, издержки могут стоить увеличения скорости.
Документ о splaysort был опубликован в Software - Practice & Experience.
источник
вставка или сортировка оболочки!
источник
Сглаживание Дейкстры отлично подходит для уже отсортированных данных. Это вариант heapsort, который работает в O (n lg n) наихудшем случае и O (n) в лучшем случае. Я написал анализ алгоритма, если вам интересно, как он работает.
Натуральная сортировка слиянием - еще один действительно хороший вариант для этого - это вариант сортировки снизу вверх, который работает, обрабатывая входные данные как конкатенацию нескольких различных отсортированных диапазонов, а затем используя алгоритм слияния для объединения их вместе. Вы повторяете этот процесс, пока весь входной диапазон не будет отсортирован. Это выполняется за O (n), если данные уже отсортированы, и O (n lg n) в худшем случае. Это очень элегантно, хотя на практике это не так хорошо, как некоторые другие адаптивные сорта, такие как Timsort или smoothsort.
источник
Если элементы уже отсортированы или имеется только несколько элементов, это был бы идеальный вариант использования Insertion Sort!
источник
Сортировка вставки занимает время O (n + количество инверсий).
Инверсия - это пара
(i, j)такая, чтоi < j && a[i] > a[j]. То есть пара не в порядке.Одной из мер «почти отсортированных» является количество инверсий - можно считать «почти отсортированные данные» для обозначения данных с небольшим количеством инверсий. Если известно, что число инверсий является линейным (например, вы только что добавили O (1) элементов в отсортированный список), сортировка вставкой занимает O (n) времени.
источник
Как и все остальные, будьте осторожны с наивной быстрой сортировкой - она может иметь производительность O (N ^ 2) для отсортированных или почти отсортированных данных. Тем не менее, с помощью соответствующего алгоритма для выбора оси (либо случайным или срединного троих - см Выбор Pivot для Quicksort ), Quicksort будет по- прежнему работать здраво.
В общем, сложность выбора таких алгоритмов, как сортировка вставки, заключается в том, чтобы решить, когда данные достаточно не в порядке, чтобы Quicksort действительно был быстрее.
источник
Я не собираюсь притворяться, что у меня есть все ответы здесь, потому что я думаю, что получение реальных ответов может потребовать кодирования алгоритмов и профилирования их по репрезентативным выборкам данных. Но я думал об этом вопросе весь вечер, и вот что мне пришло в голову до сих пор, и некоторые предположения о том, что работает лучше всего, где.
Пусть N будет общее количество элементов, M будет количество не в порядке.
Bubble sort должен сделать что-то вроде 2 * M + 1 проходов через все N предметов. Если М очень мало (0, 1, 2?), Я думаю, что это будет очень трудно победить.
Если M мало (скажем, меньше, чем log N), сортировка вставок будет иметь среднюю производительность. Тем не менее, если не будет хитрости, у меня будет очень плохая производительность в худшем случае. (Правильно? Если последний элемент в порядке идет первым, то, насколько я вижу, вам нужно вставить каждый отдельный элемент, что снизит производительность.) Я предполагаю, что для этого существует более надежный алгоритм сортировки. дело, но я не знаю, что это.
Если M больше (скажем, равно или больше, чем log N), интроспективная сортировка почти наверняка лучше.
Исключение из всего этого: если вы действительно заранее знаете, какие элементы не отсортированы, тогда вам лучше всего выбрать эти элементы, отсортировать их с помощью интроспективной сортировки и объединить два отсортированных списка в один отсортированный список. Если бы вы могли быстро выяснить, какие предметы вышли из строя, это также было бы хорошим общим решением, но я не смог найти простой способ сделать это.
Дальнейшие размышления (в одночасье): если M + 1 <N / M, то вы можете отсканировать список в поисках серии N / M в отсортированной строке, а затем развернуть этот прогон в любом направлении, чтобы найти выход из заказ товаров. Это займет не более 2N сравнений. Затем вы можете отсортировать несортированные элементы и выполнить сортировку по двум спискам. Полное сравнение должно быть меньше чем что-то вроде 4N + M log2 (M), что, я думаю, превзойдет любую неспецифическую процедуру сортировки. (Даже дальше подумал: это сложнее, чем я думал, но я все еще думаю, что это вполне возможно.)
Другая интерпретация вопроса заключается в том, что может быть много неупорядоченных элементов, но они очень близки к тому, где они должны быть в списке. (Представьте, что вы начинаете с отсортированного списка и меняете каждый другой элемент на тот, который следует за ним.) В этом случае я думаю, что сортировка пузырьков работает очень хорошо - я думаю, что число проходов будет пропорционально самому удаленному элементу. является. Сортировка вставки будет работать плохо, потому что каждый элемент не по порядку будет запускать вставку. Я подозреваю, что интроспективная сортировка или что-то подобное тоже будет хорошо работать.
источник
Если вам нужна конкретная реализация для сортировки алгоритмов, структур данных или чего-либо, что имеет ссылку на вышеперечисленное, могу ли я порекомендовать вам отличный проект «Структуры данных и алгоритмы» на CodePlex?
В нем будет все необходимое, не изобретая велосипед.
Просто моя маленькая крупинка соли.
источник
Эта хорошая коллекция алгоритмов сортировки для этой цели в ответах, кажется, не хватает сортировка Gnome , которая также подойдет и, вероятно, потребует минимальных усилий по реализации.
источник
Сортировка вставки - лучший вариант O (n) для отсортированного ввода. И это очень близко по большей части отсортированного ввода (лучше, чем быстрая сортировка).
источник
Подумай, попробуй кучу. Я считаю, что это самый последовательный из сортов O (n lg n).
источник
Bubble-sort (или, что еще безопаснее, двунаправленная пузырьковая сортировка), вероятно, идеально подходит для в основном отсортированных списков, хотя я держу пари, что измененная гребенная сортировка (с гораздо меньшим начальным размером разрыва) будет немного быстрее, когда список не будет ' Точно так же отлично отсортировано. Сортировка расчески ухудшается до сортировки пузыря.
источник
ну, это зависит от варианта использования. Если вы знаете, какие элементы изменены, удаление и вставка будут наилучшим вариантом, насколько мне известно.
источник
Сортировка пузырьков - определенно победитель. Следующим на радаре будет сортировка вставок.
источник
Держитесь подальше от быстрой сортировки - она очень неэффективна для предварительно отсортированных данных. Сортировка вставками хорошо обрабатывает почти отсортированные данные, перемещая как можно меньше значений.
источник