Алгоритм сортировки - Sorting algorithm

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

Формально результат любого алгоритма сортировки должен удовлетворять двум условиям:

  1. Вывод выполняется в монотонном порядке (каждый элемент не меньше / не больше предыдущего элемента, в соответствии с требуемым порядком).
  2. Результатом является перестановка (изменение порядка с сохранением всех исходных элементов) ввода.

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

История и концепции

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

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

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

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

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

Алгоритмы сортировки можно классифицировать по:

  • Вычислительная сложность
    • Лучшее, худшее и среднее поведение с точки зрения размера списка. Для типичных алгоритмов последовательной сортировки хорошее поведение - O ( n  log  n ), с параллельной сортировкой - O (log 2  n ), а плохое поведение - O ( n 2 ). Идеальное поведение для последовательной сортировки - O ( n ), но в среднем это невозможно. Оптимальная параллельная сортировка - O (log  n ).
    • Свопы на алгоритмы "на месте".
  • Использование памяти (и использование других ресурсов компьютера). В частности, некоторые алгоритмы сортировки « на месте ». Строго говоря, для сортировки на месте требуется только O (1) памяти помимо сортируемых элементов; иногда O (log  n ) дополнительной памяти считается "на месте".
  • Рекурсия: некоторые алгоритмы рекурсивны или нерекурсивны, в то время как другие могут быть и тем, и другим (например, сортировка слиянием).
  • Стабильность: стабильные алгоритмы сортировки поддерживают относительный порядок записей с одинаковыми ключами (т. Е. Значениями).
  • Независимо от того, являются ли они сравнением . Сортировка сравнения проверяет данные только путем сравнения двух элементов с помощью оператора сравнения.
  • Общий метод: вставка, обмен, выбор, объединение и т. Д. Сортировки обмена включают пузырьковую и быструю сортировку. Сортировка по выбору включает циклическую сортировку и динамическую сортировку.
  • Является ли алгоритм последовательным или параллельным. Остальная часть этого обсуждения почти полностью сосредоточена на последовательных алгоритмах и предполагает последовательную работу.
  • Адаптивность: влияет ли предварительная сортировка ввода на время работы. Алгоритмы, которые это учитывают, известны как адаптивные .
  • Онлайн: такой алгоритм, как Insertion Sort, в режиме онлайн, может сортировать постоянный поток ввода.

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

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

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

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

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

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

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

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

Сортировка игральных карт с помощью стабильного sort.svg

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

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

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

Виды сравнения

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

Виды сравнения
Имя Лучший В среднем Наихудший объем памяти Стабильный Метод Прочие примечания
Быстрая сортировка Нет Разбиение Быстрая сортировка обычно выполняется на месте с объемом стека O (log n ) .
Сортировка слиянием п да Слияние Высокая степень распараллеливания (до O (log n ) с использованием алгоритма трех венгров).
Сортировка слиянием на месте - - 1 да Слияние Может быть реализована как стабильная сортировка на основе стабильного слияния на месте.
Интросорт Нет Разбиение и выбор Используется в нескольких реализациях STL .
Heapsort 1 Нет Выбор
Вставка сортировки п 1 да Вставка O ( n + d ) , в худшем случае по последовательностям, имеющим d инверсий .
Блочная сортировка п 1 да Вставка и слияние Объедините блочный алгоритм слияния на месте с сортировкой слияния снизу вверх .
Тимсорт п п да Вставка и слияние Выполняет n-1 сравнений, когда данные уже отсортированы или отсортированы в обратном порядке.
Выборочная сортировка 1 Нет Выбор Стабильно с дополнительным пространством, при использовании связанных списков или при использовании в качестве варианта сортировки вставкой вместо замены двух элементов местами.
Cubesort п п да Вставка Выполняет n-1 сравнений, когда данные уже отсортированы или отсортированы в обратном порядке.
Shellsort 1 Нет Вставка Небольшой размер кода.
Пузырьковая сортировка п 1 да Обмен Крошечный размер кода.
Обменная сортировка 1 да Обмен Крошечный размер кода.
Сортировка дерева (сбалансированный) п да Вставка При использовании самобалансирующегося двоичного дерева поиска .
Цикл сортировки 1 Нет Выбор На месте с теоретически оптимальным количеством операций записи.
Сортировка библиотеки п Нет Вставка Подобно сортировке вставкой с разрывом. Это требует случайной перестановки входных данных, чтобы гарантировать с высокой вероятностью временные границы, что делает его нестабильным.
Сортировка терпения п п Нет Вставка и выбор Находит все самые длинные возрастающие подпоследовательности за O ( n log n ) .
Гладкая сортировка п 1 Нет Выбор Адаптивный вариант пирамидальной сортировки основан на последовательности Leonardo , а не традиционной двоичной кучи .
Сортировка прядей п п да Выбор
Сортировка турнира п Нет Выбор Вариант Heapsort.
Сорт шейкер для коктейлей п 1 да Обмен Вариант пузырьковой сортировки, который хорошо работает с небольшими значениями в конце списка
Сортировка гребней 1 Нет Обмен В среднем быстрее, чем пузырьковая сортировка.
Сортировка гномов п 1 да Обмен Крошечный размер кода.
Сортировка по четным и нечетным п 1 да Обмен Легко запускается на параллельных процессорах.

Несравнительные виды

В следующей таблице описаны алгоритмы целочисленной сортировки и другие алгоритмы сортировки, не являющиеся сортировками для сравнения . Таким образом, они не ограничиваются Ω ( n log n ) . Приведенные ниже сложности предполагают сортировку n элементов с ключами размера k , размера цифры d и r диапазоном сортируемых чисел. Многие из них основаны на предположении, что размер ключа достаточно велик, чтобы все записи имели уникальные значения ключа, и, следовательно, n ≪ 2 k , где ≪ означает «намного меньше». В модели машины с произвольным доступом с единичной стоимостью алгоритмы с временем выполнения , такие как сортировка по основанию, по-прежнему занимают время, пропорциональное Θ ( n log n ) , потому что n ограничено, чтобы быть не более чем , и большее количество элементов для сортировки потребуется большее k , чтобы сохранить их в памяти.

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

Также нельзя сортировать нецелые числа

Сортировка по сегменту (целочисленные ключи) - да да Если r равно , то средняя временная сложность равна .
Счетная сортировка - да да Если r равно , то средняя временная сложность равна .
LSD Radix сортировка да Нет уровни рекурсии, 2 d для массива count.

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

MSD Radix Sort - да Нет Стабильная версия использует внешний массив размера n для хранения всех ящиков.

Как и вариант LSD, он может сортировать нецелые числа.

MSD Radix Sort (на месте) - Нет Нет d = 1 для локальных уровней рекурсии, без массива счетчиков.
Сортировка спредов п Нет Нет Асимптотики основаны на предположении, что n ≪ 2 k , но алгоритм этого не требует.
Burstsort - Нет Нет Имеет лучший постоянный коэффициент, чем сортировка по основанию для сортировки строк. Хотя в некоторой степени полагается на особенности часто встречающихся строк.
Flashsort п п Нет Нет Для выполнения за линейное время требуется равномерное распределение элементов из домена в массиве. Если распределение сильно искажено, оно может стать квадратичным, если базовая сортировка квадратична (обычно это сортировка вставкой). Версия на месте нестабильна.
Почтальон сортировка - - Нет Вариант сортировки по корзине, которая работает очень аналогично MSD Radix Sort. Специально для нужд почтовой службы.

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

Другие

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

Имя Лучший В среднем Наихудший объем памяти Стабильный Сравнение Прочие примечания
Бисер сортировка п S S N / A Нет Работает только с положительными целыми числами. Требуется специализированное оборудование для гарантированной работы. Возможна программная реализация, но время выполнения будет , где S - сумма всех целых чисел, подлежащих сортировке, в случае малых целых чисел это можно считать линейным.
Блины простые - п п Нет да Счетчик - это количество переворотов.
Сортировка спагетти (опрос) п п п да Опрос Это аналоговый алгоритм с линейным временем для сортировки последовательности элементов, требующий пространства стека O ( n ), и сортировка является стабильной. Для этого требуется n параллельных процессоров. См. Раздел « Сортировка спагетти» # Анализ .
Сортировочная сеть Варьируется Варьируется Варьируется Варьируется Варьируется (стабильные сортировочные сети требуют большего количества сравнений) да Порядок сравнений устанавливается заранее на основе фиксированного размера сети.
Bitonic сортировщик параллельный параллельный непараллельный 1 Нет да Эффективный вариант Сортировочных сетей.
Богосорт п неограниченный (определенный), (ожидаемый) 1 Нет да Случайное перемешивание. Используется только в качестве примера, так как даже ожидаемое время выполнения в лучшем случае ужасно.
Stooge sort п Нет да Медленнее, чем большинство алгоритмов сортировки (даже наивных) с временной сложностью O ( n log 3 / log 1.5 ) = O ( n 2.7095 ... ). Может быть сделана стабильной, а также является сетью сортировки .
Slowsort п Нет да Алгоритм умножения и сдачи, антонимичный алгоритму « разделяй и властвуй» .

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

  • Алгоритм Торупа , рандомизированный алгоритм для сортировки ключей из домена конечного размера, занимающий время O ( n log log n ) и пространство O ( n ).
  • Алгоритм рандомизированной целочисленной сортировки , занимающий ожидаемое время и пространство O ( n ).

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

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

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

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

Простые сорта

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

Вставка сортировки

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

Выборочная сортировка

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

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

Эффективные сортировки

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

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

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

Сортировка слиянием позволяет легко объединить уже отсортированные списки в новый отсортированный список. Он начинается со сравнения каждых двух элементов (т.е. 1 с 2, затем 3 с 4 ...) и их замены, если первый должен идти после второго. Затем он объединяет каждый из результирующих списков из двух в списки из четырех, затем объединяет эти списки из четырех и так далее; пока, наконец, два списка не будут объединены в окончательный отсортированный список. Из описанных здесь алгоритмов это первый, который хорошо масштабируется до очень больших списков, потому что время его работы в худшем случае составляет O ( n log n ). Его также легко применить к спискам, а не только к массивам, поскольку он требует только последовательного доступа, а не произвольного доступа. Однако он имеет дополнительную сложность пространства O ( n ) и включает большое количество копий в простых реализациях.

Сортировка слиянием относительно недавно стала популярной в практических реализациях из-за ее использования в сложном алгоритме Timsort , который используется для стандартной процедуры сортировки в языках программирования Python и Java ( начиная с JDK7 ). Сама сортировка слиянием является стандартной процедурой в Perl , среди прочего, и используется в Java по крайней мере с 2000 года в JDK1.3 .

Heapsort

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

Быстрая сортировка

Быстрая сортировка - это алгоритм «разделяй и властвуй», основанный на операции разделения : для разделения массива выбирается элемент, называемый точкой поворота . Все элементы, меньшие, чем точка поворота, перемещаются перед ней, а все более крупные элементы перемещаются после нее. Это может быть эффективно сделано в линейное время и на месте . Затем рекурсивно сортируются меньший и больший подсписки. Это дает среднюю временную сложность O ( n log n ) с низкими накладными расходами, и, таким образом, это популярный алгоритм. Эффективные реализации быстрой сортировки (с разделением по месту) обычно являются нестабильными и довольно сложными, но на практике являются одними из самых быстрых алгоритмов сортировки. Вместе со скромным использованием пространства O (log n ) quicksort является одним из самых популярных алгоритмов сортировки и доступен во многих стандартных библиотеках программирования.

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

Shellsort

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

Shellsort был изобретен Дональдом Шелл в 1959 году. Он улучшает сортировку вставкой, перемещая элементы не по порядку более чем на одну позицию за раз. Концепция Shellsort заключается в том, что сортировка вставкой выполняется во времени, где k - это наибольшее расстояние между двумя неуместными элементами. Это означает, что обычно они выполняются за O ( n 2 ), но для данных, которые в основном отсортированы, с несколькими неуместными элементами, они работают быстрее. Таким образом, если сначала отсортировать элементы на большом расстоянии и постепенно уменьшить промежуток между элементами для сортировки, окончательная сортировка будет выполняться намного быстрее. Одна реализация может быть описана как организация последовательности данных в двумерном массиве с последующей сортировкой столбцов массива с использованием сортировки вставкой.

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

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

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

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

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

Сортировка пузырьков - это простой алгоритм сортировки. Алгоритм начинается с начала набора данных. Он сравнивает первые два элемента и, если первый больше второго, меняет их местами. Он продолжает делать это для каждой пары смежных элементов до конца набора данных. Затем он снова начинается с первых двух элементов и повторяется до тех пор, пока на последнем проходе не произойдет перестановка. Среднее время и производительность этого алгоритма в худшем случае - O ( n 2 ), поэтому он редко используется для сортировки больших неупорядоченных наборов данных. Пузырьковая сортировка может использоваться для сортировки небольшого количества элементов (где ее асимптотическая неэффективность не является большим штрафом). Пузырьковая сортировка также может быть эффективно использована в почти отсортированном списке любой длины (то есть элементы не слишком неуместны). Например, если какое-либо количество элементов неуместны только по одной позиции (например, 0123546789 и 1032547698), при обмене пузырьковой сортировкой они будут упорядочены на первом проходе, второй проход найдет все элементы по порядку, поэтому сортировка будет взять всего 2 n раз.

Сортировка гребней

Комбинированная сортировка - это относительно простой алгоритм сортировки, основанный на пузырьковой сортировке и первоначально разработанный Влодзимежем Добосевичем в 1980 году. Позднее он был заново открыт и популяризирован Стивеном Лейси и Ричардом Боксом в статье Byte Magazine, опубликованной в апреле 1991 года. Основная идея состоит в том, чтобы избавиться от черепах. , или небольшие значения в конце списка, поскольку при пузырьковой сортировке они значительно замедляют сортировку. ( Кролики , большие значения в начале списка, не представляют проблемы при пузырьковой сортировке). Это достигается путем первоначальной замены элементов, находящихся на определенном расстоянии друг от друга в массиве, а не только замены элементов, если они смежны с друг друга, а затем уменьшая выбранное расстояние до тех пор, пока оно не будет работать как обычная сортировка пузырьков. Таким образом, если Shellsort можно рассматривать как обобщенную версию сортировки вставкой, которая меняет местами элементы, расположенные на определенном расстоянии друг от друга, гребенчатую сортировку можно рассматривать как то же обобщение, которое применяется к пузырьковой сортировке.

Обменная сортировка

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

Сортировка по распределению

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

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

Подсчетная сортировка применима, когда известно, что каждый вход принадлежит определенному набору S возможностей. Алгоритм выполняется за время O (| S | + n ) и память за O (| S |), где n - длина ввода. Он работает, создавая целочисленный массив размером | S | и использование i- го бина для подсчета вхождений i- го члена S во входных данных. Затем каждый вход подсчитывается путем увеличения значения соответствующей ячейки. После этого счетный массив проходит по циклу, чтобы упорядочить все входы. Этот алгоритм сортировки часто нельзя использовать, потому что S должен быть достаточно маленьким, чтобы алгоритм был эффективным, но он чрезвычайно быстр и демонстрирует отличное асимптотическое поведение при увеличении n . Его также можно изменить для обеспечения стабильного поведения.

Ковшовая сортировка

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

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

Radix sort

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

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

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

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

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

Другой метод решения проблемы размера памяти - использование внешней сортировки , например, один из способов - объединить два алгоритма таким образом, чтобы использовать преимущества каждого из них для повышения общей производительности. Например, массив может быть разделен на фрагменты, размер которых соответствует ОЗУ, содержимое каждого фрагмента может быть отсортировано с использованием эффективного алгоритма (например, быстрой сортировки ), а результаты объединены с использованием k- образного слияния, аналогичного используемому в сортировка слиянием . Это быстрее, чем выполнять сортировку слиянием или быструю сортировку по всему списку.

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

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

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

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

Смотрите также

использованная литература

дальнейшее чтение

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