Алгоритм сортировки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

История[править | править вики-текст]

Табулятор Холлерита с «сортировальным ящиком»

Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в Соединённых Штатах Америки американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах[1]. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям, замыкалась определенная электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт[1]. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определен порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков[2]. Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов[3]. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту[4].

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ[4]. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Экертом[en] компания «Eckert–Mauchly Computer Corporation» выпустила некоторые из самых ранних электронных вычислительных машин BINAC и UNIVAC[5]. Наряду с отмеченными алгоритмами внутренней сортировки, появлялись алгоритмы внешней сортировки, развитию которых способствовал ограниченный объём памяти первых вычислительных машин[4]. В частности, были предложены методы сбалансированной двухпутевой поразрядной сортировки и сбалансированного двухпутевого слияния[5].

К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо[6]. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой[7]. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы[8].

После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки[9]. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям[9].

Формулировка задачи[править | править вики-текст]

Пусть требуется упорядочить N элементов: . Каждый элемент представляет из себя запись , содержащую некоторую информацию и ключ , управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей выполнялись следующие условия[10]:

Задачей сортировки является нахождение такой перестановки записей с индексами , после которой ключи расположились бы в порядке неубывания[10]:

Оценка алгоритма сортировки[править | править вики-текст]

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

  • Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в[11] сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2 n) операций. При этом число n должно быть заранее известно;
  • Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Оптимальность [править | править вики-текст]

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

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

Количество перестановок из элементов равно . Для того, чтобы можно было провести сюръекцию из множества ответов на сравнения на множество перестановок, количество сравнений должно быть не меньше, чем (это обеспечивается тем, что сравнение — единственная разрешённая операция[12]).

Прологарифмировав формулу Стирлинга, можно обнаружить, что

Свойства и классификация[править | править вики-текст]

  • Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами[13].
  • Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
  • Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет (), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

  • Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.
    • В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.
  • Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.
    • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
    • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

  • потребности в дополнительной памяти или её отсутствию
  • потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

Список алгоритмов сортировки[править | править вики-текст]

В этой таблице  — это количество записей, которые необходимо упорядочить, а  — это количество уникальных ключей.

Алгоритмы устойчивой сортировки[править | править вики-текст]

  • Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: .
  • Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: .
  • Гномья сортировка (англ. Gnome sort). — схожа с сортировкой пузырьком и сортировкой вставками. Сложность алгоритма — .
  • Сортировка вставками (Insertion sort) — Определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: .
  • Сортировка слиянием (Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: . Требуется дополнительной памяти.
  • Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: . Требуется дополнительной памяти.
  • Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: . Требуется дополнительной памяти. Разработан для использования в языке Python[14].
  • Сортировка подсчётом (Counting sort). Сложность алгоритма: . Требуется дополнительной памяти.
  • Блочная сортировка (Корзинная сортировка, Bucket sort) — требуется дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: .
  • Поразрядная сортировка (она же цифровая сортировка) — сложность алгоритма: ; требуется дополнительной памяти.

Алгоритмы неустойчивой сортировки[править | править вики-текст]

  • Сортировка выбором (англ. Selection sort) — поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность алгоритма: .
  • Сортировка расчёской (Comb sort) — сложность алгоритма: ; улучшение сортировки пузырьком.
  • Сортировка Шелла (Shell sort). сложность алгоритма: ; улучшение сортировки вставками.
  • Пирамидальная сортировка (сортировка кучи, Heapsort) — сложность алгоритма: ; превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка
  • Плавная сортировка (Smoothsort) — сложность алгоритма:
  • Быстрая сортировка (Quicksort), в варианте с минимальными затратами памяти — сложность алгоритма:  — среднее время,  — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании дополнительной памяти, можно сделать сортировку устойчивой.
  • Интроспективная сортировка (Introsort) — сложность алгоритма: , сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает .
  • Терпеливая сортировка (Patience sorting) — сложность алгоритма:  — наихудший случай, требует дополнительно памяти, также находит самую длинную увеличивающуюся подпоследовательность
  • Stooge sort — рекурсивный алгоритм сортировки с временной сложностью .

Непрактичные алгоритмы сортировки[править | править вики-текст]

  • Bogosort — в среднем. Произвольно перемешать массив, проверить порядок.
  • Сортировка перестановкой —  — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива.
  • Глупая сортировка (Stupid sort) — ; рекурсивная версия требует дополнительно памяти
  • Bead Sort — или , требуется специализированное аппаратное обеспечение
  • Блинная сортировка (Pancake sorting) — , требуется специализированное аппаратное обеспечение

Алгоритмы, не основанные на сравнениях[править | править вики-текст]

Прочие алгоритмы сортировки[править | править вики-текст]

Сортировка строк[править | править вики-текст]

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

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой».

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Кнут, 2007, с. 416.
  2. Кнут, 2007, с. 417.
  3. Кнут, 2007, с. 417-418.
  4. 1 2 3 Кнут, 2007, с. 418.
  5. 1 2 Кнут, 2007, с. 419.
  6. Кнут, 2007, с. 420.
  7. Кнут, 2007, с. 420-421.
  8. Кнут, 2007, с. 421.
  9. 1 2 Кнут, 2007, с. 422.
  10. 1 2 Кнут, 2007, с. 22.
  11. .
  12. Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.
  13. Кнут, 2007.
  14. Hetland, 2010.

Литература[править | править вики-текст]

  • Кнут, Д. Э. Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. Ю. В. Козаченко. — 2. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 978-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.

Ссылки[править | править вики-текст]