Спагетти сортировка

Страница 6 из 6

Страница 5 из 6

Сортировка спагетти —

Для простоты предположим, что мы сортируем список натуральные числа. Метод сортировки проиллюстрирован на сырых стержнях спагетти:

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

В Информатика, а алгоритм сортировки является алгоритм который помещает элементы список в определенном порядок. Наиболее часто используемые заказы: порядковый номер и лексикографический порядок. Эффективный сортировка важно для оптимизации эффективность других алгоритмов (например, поиск и слияние алгоритмы), которые требуют, чтобы входные данные были в отсортированных списках. Сортировка также часто бывает полезна канонизация данные и для создания удобочитаемого вывода. Более формально, вывод любого алгоритма сортировки должен удовлетворять двум условиям:

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

Алгоритмы сортировки часто называют словом, за которым следует слово «sort», и грамматически используются в английском языке как словосочетания с существительными, например, в предложении «неэффективно использовать сортировку вставкой в ​​больших списках» фраза вставка сортировки относится к вставка сортировки алгоритм сортировки.

Алгоритмы сортировки преобладают во вводных Информатика классы, где обилие алгоритмов для решения проблемы обеспечивает мягкое введение в различные основные концепции алгоритмов, такие как нотация большой O, разделяй и властвуй алгоритмы, структуры данных Такие как кучи и бинарные деревья, рандомизированные алгоритмы, лучший, худший и средний случай анализ, время-пространство компромиссы, и верхняя и нижняя границы.

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

Алгоритмы сортировки часто классифицируются по:

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

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

Стабильность важна по следующей причине: предположим, что записи учащихся, состоящие из имени и раздела класса, динамически сортируются на веб-странице, сначала по имени, затем по разделу класса во второй операции. Если в обоих случаях используется стабильный алгоритм сортировки, операция сортировки по разделам классов не изменит порядок имен; при нестабильной сортировке может случиться так, что сортировка по разделам меняет порядок имен. Используя стабильную сортировку, пользователи могут выбрать сортировку по разделу, а затем по имени, сначала сортируя по имени, а затем снова сортируя по разделу, в результате чего порядок имен сохраняется. (Некоторые программы для работы с электронными таблицами подчиняются такому поведению: сортировка по имени, затем по разделам дает алфавитный список студентов по разделам.)

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

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

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

Одним из применений стабильных алгоритмов сортировки является сортировка списка с использованием первичного и вторичного ключей. Например, предположим, что мы хотим отсортировать комбинацию карт таким образом, чтобы масти располагались в следующем порядке: трефы (♣), бубны (), сердечки (), пики (♠), и в каждой масти карты сортируются по рангу. Это можно сделать, сначала отсортировав карты по рангу (используя любую сортировку), а затем выполнив стабильную сортировку по масти:

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

В этой таблице — количество сортируемых записей. В столбцах «Среднее» и «Худшее» указано временная сложность в каждом случае при условии, что длина каждого ключа постоянна, и поэтому все сравнения, свопы и другие необходимые операции могут выполняться за постоянное время. «Память» обозначает объем вспомогательной памяти, необходимый сверх того, который используется самим списком, при том же предположении. Следует понимать, что время работы и требования к памяти, перечисленные ниже, находятся внутри нотация большой O, следовательно, основание логарифмов не имеет значения; обозначение средства .

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

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

Теоретики-информатики подробно описали другие алгоритмы сортировки, которые обеспечивают лучше, чем О(п бревно п) временная сложность, предполагающая дополнительные ограничения, в том числе:

Популярные алгоритмы сортировки

Хотя существует большое количество алгоритмов сортировки, в практических реализациях преобладает несколько алгоритмов. Сортировка вставкой широко используется для небольших наборов данных, в то время как для больших наборов данных используется асимптотически эффективная сортировка, в первую очередь сортировка по куче, сортировка слиянием или быстрая сортировка. В эффективных реализациях обычно используется гибридный алгоритм, комбинируя асимптотически эффективный алгоритм для общей сортировки с сортировкой вставкой для небольших списков в конце рекурсии. Хорошо настроенные реализации используют более сложные варианты, такие как Тимсорт (сортировка слиянием, сортировка вставкой и дополнительная логика), используемые в Android, Java и Python, и интросорт (быстрая сортировка и сортировка кучей), используется (в вариантных формах) в некоторых C ++ сортировка реализации и в .NET.

Для более ограниченных данных, таких как числа в фиксированном интервале, виды распределения такие как сортировка счётчиком или сортировка по основанию. Пузырьковая сортировка и варианты редко используются на практике, но обычно встречаются в обучении и теоретических дискуссиях.

При физической сортировке объектов (таких как алфавитные листы, тесты или книги) люди интуитивно обычно используют сортировку вставкой для небольших наборов. Для более крупных наборов люди часто сначала создают ведра, например, по начальной букве, а группирование по нескольким сегментам позволяет практически сортировать очень большие наборы. Часто пространство является относительно дешевым, например, за счет размещения объектов на полу или на большой площади, но операции дороги, особенно перемещение объекта на большое расстояние — важна местность ссылки. Сортировка слиянием также практична для физических объектов, особенно потому, что можно использовать две руки, по одной для каждого списка для слияния, в то время как другие алгоритмы, такие как сортировка кучей или быстрая сортировка, плохо подходят для использования человеком. Другие алгоритмы, такие как сортировка библиотеки, вариант сортировки вставкой, который оставляет пробелы, также практичен для физического использования.

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

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

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

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

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

Сортировка Shell отличается от пузырьковой сортировки тем, что перемещает элементы во множество меняются местами.

Наихудшая временная сложность Shellsort — это открытая проблема и зависит от используемой последовательности разрывов, с известными сложностями в диапазоне от О(п2) к О(п4/3) и Θ (п бревно2 п). Это в сочетании с тем, что Shellsort на месте, требуется только относительно небольшой объем кода и не требуется использование стек вызовов, делает его полезным в ситуациях, когда память не хватает, например, в встроенные системы и ядра операционной системы.

Пузырьковая сортировка и варианты

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

Пузырьковая сортировка, алгоритм сортировки, который непрерывно просматривает список, обмен элементы, пока они не появятся в правильном порядке.

Сортировка распределения относится к любому алгоритму сортировки, в котором данные распределяются от их ввода к нескольким промежуточным структурам, которые затем собираются и помещаются на выходе. Например, оба ведро сортировка и flashsort алгоритмы сортировки на основе распределения. Алгоритмы распределения распределения могут использоваться на одном процессоре или они могут быть распределенный алгоритм, где отдельные подмножества отдельно сортируются на разных процессорах, а затем объединяются. Это позволяет внешняя сортировка данных слишком велик, чтобы поместиться в памяти одного компьютера.

Сортировка по ведру — это разделяй и властвуй алгоритм сортировки, который обобщает счетная сортировка путем разделения массива на конечное число сегментов. Затем каждая корзина сортируется индивидуально, либо с использованием другого алгоритма сортировки, либо путем рекурсивного применения алгоритма сортировки корзин.

Сортировка по сегментам работает лучше всего, когда элементы набора данных равномерно распределены по всем сегментам.

Radix sort представляет собой алгоритм сортировки чисел путем обработки отдельных цифр. п числа, состоящие из k цифры отсортированы по O (п · k) время. Сортировка Radix может обрабатывать цифры каждого числа, начиная с младшая цифра (LSD) или начиная с самая значимая цифра (МСД). Алгоритм LSD сначала сортирует список по наименьшей значащей цифре, сохраняя при этом их относительный порядок, используя стабильную сортировку. Затем он сортирует их по следующей цифре и так далее от наименее значимого к наиболее значимому, в результате чего получается отсортированный список. В то время как поразрядная сортировка LSD требует использования стабильной сортировки, алгоритм поразрядной сортировки MSD — нет (если не требуется стабильная сортировка). Сортировка по основанию MSD на месте нестабильна. Это обычное дело для счетная сортировка алгоритм для внутреннего использования при сортировке по основанию. А гибридный подход к сортировке, такой как использование вставка сортировки для небольших ячеек значительно улучшает производительность сортировки по основанию.

Шаблоны использования памяти и сортировка индексов

Когда размер сортируемого массива приближается к доступной первичной памяти или превышает ее, так что необходимо использовать (гораздо более медленный) диск или пространство подкачки, становится важным паттерн использования памяти алгоритма сортировки, и алгоритм, который мог бы быть справедливым. эффективен, когда массив легко помещается в ОЗУ, может стать непрактичным. В этом сценарии общее количество сравнений становится (относительно) менее важным, и количество раз, когда разделы памяти должны быть скопированы или заменены на диск и с диска, может доминировать над характеристиками производительности алгоритма. Таким образом, количество проходов и локализация сравнений могут быть более важными, чем исходное количество сравнений, поскольку сравнения соседних элементов друг с другом происходят в системная шина скорость (или, с кешированием, даже при ЦПУ скорость), что по сравнению со скоростью диска практически мгновенно.

Например, популярный рекурсивный быстрая сортировка Алгоритм обеспечивает вполне разумную производительность с адекватной оперативной памятью, но из-за рекурсивного способа копирования частей массива он становится гораздо менее практичным, когда массив не помещается в ОЗУ, поскольку это может вызвать ряд медленных операций копирования или перемещения в и с диска. В этом сценарии другой алгоритм может быть предпочтительнее, даже если он требует более полных сравнений.

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

Связанные проблемы включают частичная сортировка (сортировка только k наименьшие элементы списка или, альтернативно, вычисление k наименьшие элементы, но неупорядоченные) и отбор (вычисляя kнаименьший элемент). Их можно неэффективно решить с помощью полной сортировки, но существуют более эффективные алгоритмы, часто получаемые путем обобщения алгоритма сортировки. Наиболее ярким примером является быстрый выбор, что связано с быстрая сортировка. И наоборот, некоторые алгоритмы сортировки могут быть получены путем многократного применения алгоритма выбора; быструю сортировку и быстрый выбор можно рассматривать как одно и то же поворотное движение, различающееся только тем, выполняется ли рекурсия с обеих сторон (быстрая сортировка, разделяй и властвуй ) или с одной стороны (быстрый выбор, уменьшаться и побеждать ).

Своего рода противоположность алгоритму сортировки — это алгоритм перемешивания. Они принципиально разные, потому что требуют источника случайных чисел. Перемешивание также может быть реализовано с помощью алгоритма сортировки, а именно случайной сортировки: присвоение случайного числа каждому элементу списка, а затем сортировка на основе случайных чисел. Однако на практике это обычно не делается, и существует хорошо известный простой и эффективный алгоритм перетасовки: Перемешивание Фишера – Йетса.

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

Графический пример сортировки вставками. Частично отсортированный список (черный) изначально содержит только первый элемент в списке. На каждой итерации один элемент (красный) удаляется из входных данных «еще не проверено на порядок» и вставляется на месте в отсортированный список.

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

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

Результирующий массив после k итераций имеет свойство, при котором первая k + 1 записи отсортированы («+1», потому что первая запись пропущена). На каждой итерации первая оставшаяся запись ввода удаляется и вставляется в результат в правильной позиции, таким образом расширяя результат:

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

Наиболее распространенный вариант сортировки вставкой, который работает с массивами, можно описать следующим образом:

Алгоритм также можно реализовать рекурсивно. Рекурсия просто заменяет внешний цикл, вызывая себя и сохраняя последовательно меньшие значения п в стеке, пока п равно 0, где функция затем возвращает резервную копию цепочки вызовов для выполнения кода после каждого рекурсивного вызова, начиная с п равно 1, с п увеличивается на 1, когда каждый экземпляр функции возвращается к предыдущему экземпляру. Первоначальный звонок будет insertSortR (A, длина (A) -1).

Это не делает код короче, а также не сокращает время выполнения, но увеличивает потребление дополнительной памяти от к (на самом глубоком уровне рекурсии стек содержит ссылки на А массив, каждый с сопутствующим значением переменной п из до 1).

Лучшие, худшие и средние случаи

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

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

3 7 4 9 5 2 6 13* 7 4 9 5 2 6 13 7* 4 9 5 2 6 13 4* 7 9 5 2 6 13 4 7 9* 5 2 6 13 4 5* 7 9 2 6 12* 3 4 5 7 9 6 12 3 4 5 6* 7 9 11* 2 3 4 5 6 7 9

Отношение к другим алгоритмам сортировки

Сортировка вставкой очень похожа на сортировка выбора. Как и при сортировке выбора, после k проходит через массив, первый k элементы в отсортированном порядке. Однако фундаментальное различие между этими двумя алгоритмами состоит в том, что сортировка вставкой сканирует назад от текущего ключа, а сортировка выбором сканирует вперед. Это приводит к сортировке выбора, в результате чего первые k элементов k наименьшие элементы несортированного ввода, тогда как при сортировке вставкой они просто первые k элементы ввода.

Основным преимуществом сортировки вставкой перед сортировкой выбора является то, что сортировка выбора всегда должна сканировать все оставшиеся элементы, чтобы найти абсолютный наименьший элемент в несортированной части списка, в то время как сортировка вставкой требует только одного сравнения, когда (k + 1) -й элемент больше, чем k-й элемент; когда это часто бывает так (например, если входной массив уже отсортирован или частично отсортирован), сортировка вставкой явно более эффективна по сравнению с сортировкой по выбору. В среднем (исходя из ранга (k + 1) -й ранг элемента является случайным), сортировка вставкой потребует сравнения и сдвига половины предыдущего k элементов, что означает, что сортировка вставкой в ​​среднем будет выполнять примерно вдвое меньше сравнений, чем сортировка по выбору.

В худшем случае для сортировки вставкой (когда входной массив отсортирован в обратном порядке) сортировка вставкой выполняет столько же сравнений, что и сортировка выбора. Однако недостатком сортировки вставкой перед сортировкой выбора является то, что она требует большего количества записей из-за того, что на каждой итерации вставка (k + 1) -й элемент в отсортированной части массива требует замены множества элементов для сдвига всех следующих элементов, в то время как для каждой итерации сортировки выбора требуется только одна замена. В общем случае сортировка вставкой будет записывать в массив O (п2) раз, тогда как сортировка выбора будет писать только O () раз. По этой причине сортировка выбора может быть предпочтительнее в случаях, когда запись в память значительно дороже чтения, например, с EEPROM или же флэш-память.

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

Чтобы избежать необходимости выполнять серию свопов для каждой вставки, ввод можно сохранить в связанный список, который позволяет вставлять элементы в список или из него в постоянное время, когда позиция в списке известна. Однако поиск в связанном списке требует последовательного перехода по ссылкам в желаемую позицию: связанный список не имеет произвольного доступа, поэтому он не может использовать более быстрый метод, такой как двоичный поиск. Следовательно, время, необходимое для поиска, равно O (п), а время сортировки — O (п2). Если более сложный структура данных (например., куча или же двоичное дерево ) можно значительно сократить время, необходимое для поиска и вставки; это суть куча сортировки и двоичная сортировка дерева.

Если пропустить список время вставки сокращается до O (logп), и свопы не нужны, потому что список пропуска реализован в структуре связанного списка. Окончательное время вставки будет O (п бревноп).

Код сортировки вставки списка в C

Если элементы хранятся в связанном списке, то список можно отсортировать с O (1) дополнительным пространством. Алгоритм начинается с изначально пустого (и, следовательно, тривиально отсортированного) списка. Элементы ввода удаляются из списка по одному, а затем вставляются в нужное место в отсортированном списке. Когда список ввода пуст, отсортированный список имеет желаемый результат.

// ноль или один элемент в списке // head — первый элемент итогового отсортированного списка // вставляем в начало отсортированного списка // или как первый элемент в пустой отсортированный список // вставляем текущий элемент в нужную позицию в непустом отсортированном списке // последний элемент отсортированного списка // середина списка // вставить в середину отсортированного списка или как последний элемент

// ноль или один элемент в списке / * строим отсортированный массив из пустого списка * / / * берем элементы из входного списка один за другим, пока он не станет пустым * / / * запоминаем голову * / / * конечный указатель для эффективного монтажа * / / * выскакивать список * / / * вставляем голову в отсортированный список в нужном месте * / / * здесь голова? * / / * нет — продолжить вниз по списку * /

Сортировка спагетти — это линейный, аналог алгоритм для сортировки последовательности элементов, представленный Александром Дьюдни в его колонке Scientific American. Этот алгоритм стабильно сортирует последовательность элементов, требующих пространства стека O (n). Требуется параллельный процессор.

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

Анализ

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

Внешние ссылки

Последняя правка сделана 2021-06-09 01:24:07

Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).

Алгоритм, упорядочивающий списки в порядке

В информатике, Алгоритм сортировки — это алгоритм, который помещает элементы списка в определенный порядок. Наиболее часто используемые порядки — это числовой порядок и лексикографический порядок. Эффективная сортировка важна для оптимизации эффективности других алгоритмов (таких как поиск и алгоритмы слияния ), которые требуют, чтобы входные данные были в отсортированных списки. Сортировка также часто бывает полезна для канонизации данных и для получения удобочитаемых результатов. Более формально, выходные данные любого алгоритма сортировки удовлетворять двум условиям:

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

История

С самого начала вычислений проблема сортировки привлекает большое количество исследования, возможно, из-за сложности ее эффективного решения, несмотря на простую, знакомую формулировку. Среди авторов ранних алгоритмов сортировки около 1951 года была Бетти Холбертон (урожденная Снайдер), которая работала над ENIAC и UNIVAC. Сортировка пузырьков был проанализирован еще в 1956 году. Основным требованием алгоритмов сортировки сравнений является Ω (n log n) сравнений (для некоторых входных последовательностей потребуется число сравнений, кратное n log n, где n — количество элементов в сортируемый массив). Алгоритмы, не основанные на сравнении, такие как сортировка с подсчетом, могут иметь лучшую производительность. Астотически оптимальные алгоритмы были известны с середины 20 века — новые полезные алгоритмы все еще изобретаются, при этом широко используем сейчас Timsort датируется 2002 годом, библиотека sort впервые опубликована в 2006 году.

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

Оптимальная сортировка небольших массивов (при минимальном количестве сравнений и свопы) или быстро (т. е. с учетом специфики машины) все еще остается открытой исследовательской проблемой, решения которой известны только для очень маленьких массивов (<20 elements). Similarly optimal (by various definition) sorting on a parallel machine is an open research topic.

Классификация

Сортировка g алгоритмы часто классифицируются по:

Стабильность

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

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

Стабильность важна по следующей причине: предположим, что записи учащихся, состоящие из имени и раздела класса, динамически сортируются на странице-странице, сначала по имени, по разделу класса во второй операции. Если в обоих случаях используется стабильный алгоритм сортировки, операция сортировки по разделам классов не изменит порядок имен; при нестабильной сортировке может случиться так, что сортировка по разделам меняет порядок имен. Используя стабильную сортировку, пользователи могут выбрать сортировку по разделу, а затем по имени, сначала сортируя по имени, а затем снова сортируя по разделу, в результате чего порядок имен сохраняется. (Некоторые программы для работы с электронными таблицами подчиняются такому поведению: сортировка по имени, затем по разделам дает алфавитный список студентов по разделам.)

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

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

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

Одно из применений стабильных алгоритмов сортировки — это сортировка списка с использованием первичного и вторичного ключей. Например, предположим, что мы хотим отсортировать комбинацию карт таким образом, чтобы масти располагались в следующем порядке: трефы (), бубны (♦), червы (♥) (♠), и в каждой масти карты отсортированы по ранг. Это можно сделать, сначала отсортировав карты по рангу (используя любую сортировку), а затем выполнив стабильную сортировку по рангу:

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

Сравнение алгоритмов

В этой таблице n — количество записей для сортировки. Столбцы «Среднее» и «Худшее» дают временную сложность в каждом случае при условии, что длина каждого ключа постоянна, и, следовательно, все сравнения, свопы и другие операции в постоянном времени. «Память» обозначает объем вспомогательной памяти, необходимый сверх того, который используется самим списком, при том же предположении. Следует понимать, что время выполнения и требований к памяти, перечисленные ниже, находятся внутри большие нотации O, поэтому основание логарифмов не имеет значения; запись log n означает (log n).

Сортировки сравнения

Ниже представлена ​​таблица сортировки сравнения. Сортировка сравнения не может быть лучше, чем O (n log n).

Сортировка без сравнения

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

Прочие

Некоторые алгоритмы медленны по сравнению с описанными выше, например, bogosort с неограниченным временем выполнения и stooge sort с O (n) время работы. Эти виды обычно описываются в образовательных целях, чтобы продемонстрировать, как оценивается время выполнения алгоритмов. В следующей таблице описаны некоторые алгоритмы сортировки, которые непрактичны для реального использования в традиционных контекстах программного обеспечения из-за крайне низкой производительности или специальных требований к оборудованию.