Открыть главное меню

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

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

Содержание

ИсторияПравить

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

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

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ[4]. Первым опубликованным обсуждением сортировки с помощью вычислительных машин стала лекция Джона Мокли, прочитанная им в 1946 году. Мокли показал, что сортировка может быть полезной также и для численных расчетов, описал методы сортировки простой вставки и бинарных вставок, а также поразрядную сортировку с частичными проходами. Позже организованная им совместно с инженером Джоном Эккертом компания «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].

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

 

Сортировка называется устойчивой, если не меняет взаимного расположения элементов с одинаковыми ключами[10]:

  для любых   и  .

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

Оценка алгоритма сортировкиПравить

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

  • Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (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). Сложность алгоритма:  .
  • Сортировка вставками (англ. Insertion sort) — определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма:  .
  • Гномья сортировка (англ. Gnome sort; первоначально опубликована под названием «глупая сортировка» [stupid sort] за простоту реализации) — сходна с сортировкой вставками. Сложность алгоритма —  ; рекурсивная версия требует дополнительно   памяти.
  • Сортировка слиянием (англ. Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма:  . Требуется   дополнительной памяти.
  • Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма:  . Требуется   дополнительной памяти.
  • Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма:  . Требуется   дополнительной памяти. Разработан для использования в языке Python[14].

Алгоритмы неустойчивой сортировкиПравить

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

Непрактичные алгоритмы сортировкиПравить

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

Алгоритмы, не основанные на сравненияхПравить

  • Блочная сортировка (Корзинная сортировка, англ. Bucket sort) — требуется   дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма:  .
  • Поразрядная сортировка (она же цифровая сортировка, англ. Radix sort) — сложность алгоритма:  ; требуется   дополнительной памяти.
  • Сортировка подсчётом (англ. Counting sort). Сложность алгоритма:  . Требуется   дополнительной памяти.

Прочие алгоритмы сортировкиПравить

Сортировка строкПравить

Одним из наиболее частых приложений алгоритмов сортировки является сортировка строк. Обычно она производится так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины 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 3 4 Кнут, 2007, с. 22.
  11. Кнут, 2007, с. 23.
  12. Дональд Кнут. 5.3.1. Сортировка с минимальным числом сравнений // Искусство программирования. — 2-е. — Вильямс, 2002.
  13. Кнут, 2007.
  14. Hetland, 2010.

ЛитератураПравить

  • Кнут Д. Э. Искусство программирования. Том 3. Сортировка и поиск = 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.

СсылкиПравить