Файл: Алгоритмы сортировки данных (Теоретические основы).pdf

Введение

Сортировкой называют процесс перегруппировки заданного множества объектов в некотором определенном порядке. Сортировка (sorting) — распределение по сортам, деление на категории. Программисты используют более узкий термин — упорядочение (ordering), однако использование этого слова может привести к путанице из-за перегруженности слова «порядок». Ранжирование (sequencing) не всегда отражает суть дела, особенно если есть равные элементы. Часто используются все три термина с одним и тем же смыслом.

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

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

Объектом исследования являются направления реализации алгоритмов сортировки данных.

Предмет исследования – алгоритмы сортировки данных.

Целью исследования в работе является углубленное изучение основных алгоритмов сортировки данных.

Для достижения поставленной цели сформулированы следующие задачи:

1. изучить теоретические основы методов сортировки;
2. описать основные методы сортировки данных;
3. рассмотреть перспективы развития методов сортировки.

Методологической основой исследования являются учебная и методическая литература, статьи в периодической печати и Интернет-ресурсы.

1. Теоретические основы алгоритмов сортировки. Исторический аспект появления и развития методов сортировки

---

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

В дальнейшем история алгоритмов оказалась связана с развитием электронно-вычислительных машин. По некоторым источникам, именно программа сортировки стала первой программой для вычислительных машин. Некоторые конструкторы ЭВМ, в частности разработчики EDVAC, называли задачу сортировки данных наиболее характерной нечисловой задачей для вычислительных машин. В 1945 году Джон фон Нейман для тестирования ряда команд для EDVAC разработал программы сортировки методом слияния. В том же году немецкий инженер Конрад Цузе разработал программу для сортировки методом простой вставки. К этому времени уже появились быстрые специализированные сортировальные машины, в сопоставлении с которыми и оценивалась эффективность разрабатываемых ЭВМ.

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

---

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

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

2. Математическая постановка задачи для сортировки данных

Пусть требуется упорядочить N элементов:  R₁,R_{2, …}, R_n Каждый элемент представляет из себя запись R_j, содержащую некоторую информацию и ключ K_j, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей a, b, c выполнялись следующие условия[10]:

---

1. закон трихотомии: либо a<b, либо  a> b, либо  a=b;
2. закон транзитивности: если a<b и b<c, то  a<c.

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

Задачей сортировки является нахождение такой перестановки записей p(1), p(2), …, p(n) с индексами 1,2, … ,N, после которой ключи расположились бы в порядке неубывания [10]:

K_p(1) ≤ K_p(2) ≤… ≤ K_p(n)

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

p(i)<p(j)} для любых  K_p(i) = K_p(j) и  i<j.

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

Характеристика алгоритмов сортировки

3. Алгоритм сортировки методом пузырька и прямым выбором

Одним из простейших алгоритмов сортировки является сортировка пузырьком (BubbleSort).

Название метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает») (рис.1).

Рис.1. Нулевой проход. Сравниваемые пары и обмены выделены

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

Вместо поднятия самого «легкого» элемента можно «топить» самый «тяжелый».

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

Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.

Сложность алгоритма сортировки пузырьком составляет О(N2), количество операций сравнения: N х (N — 1)/2. Это очень плохая сложность, но алгоритм имеет два плюса.

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

---

Рис.2. Номер прохода. Отсортированная часть выделена полосой

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

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

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

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

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

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

4. Эффективные алгоритмы сортировки

Начнем рассмотрение эффективных алгоритмов сортировки (работающих за O(N log N)) с пирамидальной сортировки, в которой используются знакомые нам идеи кучи.

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

Напомним свойство кучи максимумов: элементы с индексами i+ 1 и i + 2 не больше, чем элемент с индексом i (естественно, если i + 1 и i + 2 лежат в пределах кучи). Пусть n — размер кучи, тогда вторая половина массива (элементы от n/2 + 1 до n) удовлетворяют свойству кучи. Для остальных элементов вызовем функцию «проталкивания» по куче, начиная с n/2 до 0.

---