Файл: Углубленное изучение основных алгоритмов сортировки данных.pdf
Добавлен: 23.05.2023
Просмотров: 94
Скачиваний: 2
Введение
Сортировкой называют процесс перегруппировки заданного множества объектов в некотором определенном порядке. Сортировка (sorting) — распределение по сортам, деление на категории. Программисты используют более узкий термин — упорядочение (ordering), однако использование этого слова может привести к путанице из-за перегруженности слова «порядок». Ранжирование (sequencing) не всегда отражает суть дела, особенно если есть равные элементы. Часто используются все три термина с одним и тем же смыслом.
Алгоритм сортировки — это алгоритм для упорядочивания элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
Цель сортировки — облегчение последующего поиска элементов в отсортированном множестве во внутренней или внешней памяти. В последнем случае она особенно важна, если имеется только последовательный доступ к файлам (появляется возможность приемлемой замены прямого доступа). Сортировка и поиск в той или иной мере присутствуют во всех приложениях. При обработке больших объемов данных эффективность именно этих операций определяет эффективность, а иногда и работоспособность всей системы.
Объектом исследования являются направления реализации алгоритмов сортировки данных.
Предмет исследования – алгоритмы сортировки данных.
Целью исследования в работе является углубленное изучение основных алгоритмов сортировки данных.
Для достижения поставленной цели сформулированы следующие задачи:
- изучить теоретические основы методов сортировки;
- описать основные методы сортировки данных;
- рассмотреть перспективы развития методов сортировки.
Методологической основой исследования являются учебная и методическая литература, статьи в периодической печати и Интернет-ресурсы.
Теоретические основы алгоритмов сортировки
Первые прототипы современных методов сортировки появились уже в 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]. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям.
Пусть требуется упорядочить N элементов: R1,R2, …, Rn Каждый элемент представляет из себя запись Rj, содержащую некоторую информацию и ключ Kj, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей a, b, c выполнялись следующие условия[10]:
- закон трихотомии: либо a<b, либо a> b, либо a=b;
- закон транзитивности: если a<b и b<c, то a<c.
Данные условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке большинством методов[10].
Задачей сортировки является нахождение такой перестановки записей p(1), p(2), …, p(n) с индексами 1,2, … ,N, после которой ключи расположились бы в порядке неубывания [10]:
Kp(1) ≤ Kp(2) ≤… ≤ Kp(n)
Сортировка называется устойчивой, если не меняет взаимного расположения элементов с одинаковыми ключами [10]:
p(i)<p(j)} для любых Kp(i) = Kp(j) и i<j.
Методы сортировки можно разделить на внутренние и внешние. Внутренняя сортировка используется для данных, помещающихся в оперативную память, за счёт чего является более гибкой в плане структур данных. Внешняя сортировка применяется, когда данные в оперативную память не помещаются, и ориентирована на достижение результата в условиях ограниченных ресурсов[11].
Характеристика алгоритмов сортировки
Одним из простейших алгоритмов сортировки является сортировка пузырьком (BubbleSort).
Название метода отражает его сущность: на каждом шаге самый «легкий» элемент поднимается до своего места («всплывает») (рис.1).
Рис.1. Нулевой проход. Сравниваемые пары и обмены выделены
Для этого мы просматриваем все элементы снизу вверх, берем пару соседних элементов и, в случае, если они стоят неправильно, меняем их местами.
Вместо поднятия самого «легкого» элемента можно «топить» самый «тяжелый».
Т.к. за каждый шаг на свое место встает ровно 1 элемент (самый «легкий» из оставшихся), то нам потребуется выполнить N шагов (рис.2).
Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.
Сложность алгоритма сортировки пузырьком составляет О(N2), количество операций сравнения: N х (N — 1)/2. Это очень плохая сложность, но алгоритм имеет два плюса.
Во-первых, он легко реализуется, а значит, может и должен применяться в тех случаях, когда требуется однократная сортировка массива. При этом размер массива не должен быть больше 10000, т.к. иначе алгоритм сортировки пузырьком не будет укладываться в отведенное время.
Рис.2. Номер прохода. Отсортированная часть выделена полосой
Во-вторых, сортировка пузырьком использует только сравнения и перестановки соседних элементов, а значит, может использоваться в тех задачах, где явно разрешен только такой обмен и для сортировки, например, списков.
Существуют разнообразные «оптимизации» сортировки пузырьком, которые усложняют (а нередко и увеличивают время работы алгоритма), но не приносят выгоды ни в плане сложности, ни в плане быстродействия.
На этом плюсы сортировки пузырьком заканчиваются. В дальнейшем мы еще более сузим область применения сортировки пузырьком.
Рассмотрим еще один квадратичный алгоритм, который, однако, является оптимальным по количеству присваиваний и может быть использован, когда по условию задачи необходимо явно минимизировать количество присваиваний.
Суть метода заключается в следующем: мы будем выбирать минимальный элемент в оставшейся части массива и приписывать его к уже отсортированной части. Повторив эти действия N раз, мы получим отсортированный массив.
Количество сравнений составляет О(N2), а количество присваиваний всего О(N). В целом это плохой метод, и он должен быть использован только в случаях, когда явно необходимо минимизировать количество присваиваний.
Начнем рассмотрение эффективных алгоритмов сортировки (работающих за O(N log N)) с пирамидальной сортировки, в которой используются знакомые нам идеи кучи.
Мы будем выбирать из кучи самый большой элемент, и записывать его в начало уже отсортированной части массива (сортировка выбором в обратном порядке). Т.е. отсортированный массив будет строиться от конца к началу. Такие ухищрения необходимы, чтобы не было необходимости в дополнительной памяти и для ускорения работы алгоритма — куча будет располагаться в начале массива, а отсортированная часть будет находиться после кучи.
Напомним свойство кучи максимумов: элементы с индексами i+ 1 и i + 2 не больше, чем элемент с индексом i (естественно, если i + 1 и i + 2 лежат в пределах кучи). Пусть n — размер кучи, тогда вторая половина массива (элементы от n/2 + 1 до n) удовлетворяют свойству кучи. Для остальных элементов вызовем функцию «проталкивания» по куче, начиная с n/2 до 0.
Эта функция получает указатель на массив, номер элемента, который необходимо протолкнуть и размер кучи. У нее есть небольшие отличия от обычных функций работы с кучей. Номер минимального предка хранится в переменной y, если необходимость в обменах закончена, то мы выходим из цикла и записываем просеянную переменную на предназначенное ей место.
Сама сортировка будет состоять из создания кучи из массива и N переносов элементов с вершины кучи с последующим восстановлением свойства кучи:
Всего в процессе работы алгоритма будет выполнено 3 х N/2 — 2 вызова функции down_heap, каждый из которых занимает O(logN). Таким образом, мы и получаем искомую сложность в O(N logN), не используя при этом дополнительной памяти. Количество присваиваний также составляет O(N logN).
Пирамидальную сортировку следует осуществлять, если из условия задачи понятно, что единственной разрешенной операцией является «проталкивание» элемента по куче, либо в случае отсутствия дополнительной памяти.
Другим эффективным алгоритмом сортировки является метод быстрой сортировки. Мы уже рассматривали идеи, которые используются в быстрой сортировке, при поиске порядковых статистик. Точно так же, как и в том алгоритме, мы выбираем некий опорный элемент и все числа, меньшие его перемещаем в левую часть массива, а все числа большие его — в правую часть. Затем вызываем функцию сортировки для каждой из этих частей.
Таким образом, наша функция сортировки должна принимать указатель на массив и две переменные, обозначающие левую и правую границу сортируемой области.