Interested Article - Алгоритм сортировки
- 2020-07-06
- 1
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент в списке имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
История
Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах . У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определённая электрическая цепь , и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт . Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки . В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определён порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков . Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов . К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту .
В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин . По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC , называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния . В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки . К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ . Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли , прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчётов, описал методы сортировки простой вставки и бинарных вставок , а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания « Eckert–Mauchly Computer Corporation » выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC . Наряду с отмеченными алгоритмами внутренней сортировки , появлялись алгоритмы внешней сортировки , развитию которых способствовал ограниченный объём памяти первых вычислительных машин . В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния .
К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо . В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой . Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки , предложив некоторые новые методы .
После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние со вставкой, обменная поразрядная сортировка , каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки . Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям .
Формулировка задачи
Пусть требуется упорядочить N элементов: . Каждый элемент представляет собой запись , содержащую некоторую информацию и ключ , управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей выполнялись следующие условия :
- : либо , либо , либо ;
- закон транзитивности : если и , то .
Данные условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке большинством методов .
Задачей сортировки является нахождение такой перестановки записей с индексами , после которой ключи расположились бы в порядке неубывания :
Сортировка называется устойчивой , если не меняет взаимного расположения элементов с одинаковыми ключами :
- для любых и .
Методы сортировки можно разделить на внутренние и внешние . Внутренняя сортировка используется для данных, помещающихся в оперативную память, за счёт чего является более гибкой в плане структур данных. При внешней сортировке данные в оперативную память не помещаются, и она ориентирована на достижение результата в условиях ограниченных ресурсов .
Оценка алгоритма сортировки
Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:
- Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью . Для упорядочения важны худшее , среднее и лучшее поведение алгоритма в терминах мощности входного множества A . Если на вход алгоритму подаётся множество A , то обозначим n = | A |. Для типичного алгоритма хорошее поведение — это O ( n log n ) и плохое поведение — это O ( n 2 ) . Идеальное поведение для упорядочения — O ( n ) . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей, всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O ( n log log n ) , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О -обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике) . Также существует понятие сортирующих сетей . Предполагая, что можно одновременно (например, при параллельном вычислении ) проводить несколько сравнений, можно отсортировать n чисел за O (log 2 n ) операций. При этом число n должно быть заранее известно;
- Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O (log n ) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O (1) ). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте .
Оптимальность O ( n log n ) в общем случае
В общем случае задача сортировки предполагает, что единственной обязательно доступной операцией над элементами является сравнение. Ответом на сравнение элементов и может быть один из двух вариантов: или . Поэтому если в ходе работы алгоритм совершает сравнений, то всего возможно вариантов комбинаций ответов на них.
Количество перестановок из элементов равно . Для того, чтобы можно было сюръективно отобразить множество комбинаций ответов на множество всех перестановок, количество сравнений должно быть не меньше, чем (поскольку сравнение — единственная разрешённая операция).
Прологарифмировав формулу Стирлинга , можно обнаружить, что
Свойства и типы
- Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами .
- Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
- Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоёмкость худшего случая для этих алгоритмов составляет ( ), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.
Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:
-
Внутренняя сортировка
оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.
- В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
-
Внешняя сортировка
оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.
- Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
- Объём данных не позволяет им разместиться в ОЗУ.
Также алгоритмы классифицируются по:
- потребности в дополнительной памяти или её отсутствию
- потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой
Обзор наиболее популярных алгоритмов сортировки
|
Этот раздел
не завершён
.
|
Алгоритм | Описание | Время исполнения | Затраты памяти | Примечание | |
---|---|---|---|---|---|
В худшем случае | В среднем | В лучшем случае | |||
Алгоритмы устойчивой сортировки | |||||
Сортировка пузырьком ( англ. Bubble sort ) | Проходит по массиву, сравнивает последовательные пары элементов и меняет их местами, если они расположены в неправильном порядке. | В процессе сортировки минимальный элемент "всплывает" вверх массива, напоминая пузырь | |||
Сортировка перемешиванием ( англ. Cocktail sort ) | Двунаправленный, оптимизированный вариант сортировки пузырьком | ||||
Сортировка вставками ( англ. Insertion sort ) | Элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов | ||||
Гномья сортировка ( англ. Gnome sort ) | Гибрид сортировок вставками и пузырьком . | Название происходит от предполагаемого поведения садовых гномов при сортировке линии садовых горшков | |||
Сортировка слиянием ( англ. Merge sort ) | Рекурсивно сортирует половины массива, а затем комбинирует их в один | ||||
Сортировка с помощью двоичного дерева ( англ. Tree sort ) | На основе исходных данных строится двоичное дерево поиска , в котором последовательно собираются минимальные значения | ||||
Сортировка Timsort ( англ. Timsort ) | Гибрид сортировок вставками и слиянием . Основан на предположении, что при решении практических задач входной массив зачастую состоит из отсортированных подмассивов | ||||
Алгоритмы неустойчивой сортировки | |||||
Сортировка выбором ( англ. Selection sort ) | Делит входной массив на упорядоченную и неупорядоченную части. Затем последовательно переносит в первую часть наименьшие элементы из второй | ||||
Сортировка расчёской ( англ. Comb sort ) | Модификация сортировки пузырьком , в которой расстояние между сравниваемыми парами значений отлично от 1 | Несмотря на бóльшую алгоритмическую сложность , при не очень больших размерах массива сортировка расчёской будет более эффективна чем быстрая сортировка | |||
Сортировка Шелла ( англ. Shell sort ) | Модификация сортировки вставками , в которой расстояние между сравниваемыми парами значений отлично от 1 | ||||
Пирамидальная сортировка (сортировка кучи, Heapsort) | На основе исходных данных строится двоичная куча , в которой последовательно собираются минимальные значения | ||||
Плавная сортировка ( англ. Smoothsort ) | Модификация пирамидальной сортировки , оптимизирующая сортировку частично упорядоченного массива | ||||
Быстрая сортировка ( англ. Quicksort ) | Выбирается опорный элемент p. Все ключи меньшие p перемещаются влево от него, а все ключи большие либо равные p, вправо. Далее алгоритм рекурсивно применяется к каждой из частей | ||||
Интроспективная сортировка ( англ. Introsort ) | Гибрид быстрой и пирамидальной сортировок | ||||
Придурковатая сортировка ( англ. Stooge sort ) | Меняет местами первый и последний элементы массива, если необходимо. Затем делит массив на три части, в каждой из которых запускается рекурсивно |
|
Метод назван в честь американской комик-группы "Three stooges" ("Три придурка"). Сходство заключается в том, что алгоритм безумно мечется по уже отсортированным третям массива. | ||
Непрактичные алгоритмы сортировки | |||||
Bogosort | Массив произвольно перемешивается до тех пор, пока не окажется отсортированным | Неограниченно | Используется только в академических целях | ||
Генерируются все возможные последовательности массива, из которых выбирается упорядоченная | Используется только в академических целях | ||||
Гравитационная сортировка ( англ. Bead sort ) | Числа представляются в виде бусинок на штырях, затем сортируются под действием гравитации | Требуется специализированное аппаратное обеспечение | |||
Алгоритмы, не основывающиеся на сравнениях | |||||
Блочная сортировка ( англ. Bucket sort ) | Элементы распределяются по блокам согласно диапазону значений, каждый из которых затем рекурсивно сортируется | - заранее известное количество корзин | |||
Поразрядная сортировка ( англ. Radix sort ) | Массив сортируется согласно с помощью поразрядного сравнения чисел | — количество бит, требуемых для хранения каждого ключа. | |||
Сортировка подсчётом ( англ. Counting sort ) | Подсчитывается количество вхождений каждого целого числа из диапазона ключей в массив. Затем выводится значения всех ненулевых значений | - максимальное значение элементов ключа |
Сортировка строк
Одним из частых приложений алгоритмов сортировки является сортировка строк. Обобщённый алгоритм может выглядеть так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины N со строкой длины N+1) считается меньше любого символа.
Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой». Также на практике эффективным способом решения проблемы сортировки строк, содержащих числа, является добавление некоторого числа нулей перед числом, таким образом, «011» будет считаться больше «009».
См. также
Примечания
- ↑ , с. 416.
- , с. 417.
- , с. 417-418.
- ↑ , с. 418.
- ↑ , с. 419.
- , с. 420.
- , с. 420-421.
- , с. 421.
- ↑ , с. 422.
- ↑ , с. 22.
- , с. 23.
- Han, Yijie. (англ.) // Journal of Algorithms. Cognition, Informatics and Logic. — 2004. — Т. 50 , № 1 . — С. 96-105 . — doi : . 12 ноября 2020 года.
- Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.
- .
Литература
- Кнут Д. Э. = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1 .
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М. : , 2006. — С. 1296. — ISBN 5-8459-0857-4 .
- Роберт Седжвик. Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб. : ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4 .
- Magnus Lie Hetland. Python Algorithms: Mastering Basic Algorithms in the Python Language. — Apress, 2010. — 336 с. — ISBN 978-1-4302-3237-7 .
Ссылки
- (англ.)
- 2020-07-06
- 1