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

В статье был рассмотрен целый ряд новых алгоритмов сортировки, в т. ч. способ бинарных вставок. До середины 1950-х гг. самыми популярными были модификации сортировки вставками и слиянием сложности O (n log n) для n элементов. Еще одним результатом перехода к сортировке данных при помощи ЭВМ явилось разделение сортировки на два вида — внутреннюю и внешнюю, то есть на не использующую и использующую данные, расположенные на периферийных устройствах [9, с. 37].

В середине 1950-х гг. с разработкой ЭВМ II поколения началось активное развитие алгоритмов сортировки. Главными предпосылками для этого явились, во-первых, серьезное ускорение и упрощение написания программ для компьютеров в результате разработки первых языков программирования высокого уровня (Алгол, Фортран, Кобол); во-вторых, серьезное увеличение доступности компьютеров в результате резкого снижения их стоимости и габаритов и, как следствие, очень широкое их распространение; в-третьих, повышение производительности компьютеров до 30 000 операций в секунду.

В 1959 г. Д. Л. Шелл предложил способ сортировки с убывающим шагом, в 1960 г. Ч. Э. Р. Хоар — способ быстрой сортировки, в 1964 г. Дж. У. Дж. Уильямс — способ пирамидальной сортировки. Многие из появившихся в данный период алгоритмов (к примеру, быстрая сортировка Хоара) широко используются и в настоящее время [18, с. 245].

Итоги данного этапа активного развития алгоритмов сортировки подвел в 1973 г. Д. Э. Кнут в третьем томе своей фундаментальной монографии «Искусство программирования.

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

Наибольшее число разработанных к этому времени методов относилось к сортировке путем вставок (бинарные и двухпутевые вставки, метод простых вставок, метод Шелла, сортировка с вычислением адреса, вставка в список и пр.), обменной сортировке (метод пузырька и его модификации, быстрая сортировка, параллельная сортировка Бэтчера, асимптотические методы, обменная поразрядная сортировка) и сортировке посредством выбора (пирамидальная сортировка, выбор из дерева, метод связанного представления приоритетных очередей, метод исключения наибольшего из включенных). Не менее активно разрабатывались и методы внешней сортировки, в т. ч. методы многопутевого слияния и выбора с замещением, каскадного слияния, многофазного слияния, внешней поразрядной сортировки, осциллирующей сортировки и т. д. [9, с. 41].

Очередной всплеск интереса к алгоритмам сортировки происходит в середине 1970-х гг., когда элементной базой компьютеров стали большие интегральные схемы и появилась возможность объединения мощности вычислительных машин путем создания единых вычислительных центров, позволяющих работать с разделением времени. В период с середины 1970-х до 1990-х гг. были достигнуты серьезные успехи в повышении скорости сортировки за счет увеличения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. Например, нидерландский ученый Э. В. Дейкстра в 1981 г. предложил алгоритм плавной сортировки, который является развитием пирамидальной сортировки [6, с. 75].

Вторым направлением усовершенствования алгоритмов сортировки стал поиск оптимальных входных последовательностей для различных методов сортировки, что дало возможность серьезно уменьшить ее время. Третьим направлением, наиболее интенсивно развивающимся, было решение задачи сортировки в классе параллельных алгоритмов, для чего не только обобщались ранее известные парадигмы, но и разрабатывались принципиально новые алгоритмы. Развитие этого направления стимулировалось и все более широким использованием сортирующих сетей, а также многомерных вычислительных решеток [9, с. 43].

Для текущего этапа развития методов и способов сортировки характерно исследование задач сортировки на частично упорядоченных множествах: задач распознавания частично упорядоченного множества М; задач сортировки частично упорядоченного множества М с использованием результатов попарных сравнений элементов, а также задач определения порядка на множестве М без априорной информации. Актуальность этих задач обусловлена распространением и появлением компьютеров на сверхсложных микропроцессорах с параллельно-векторной структурой, высокоэффективных сетевых компьютерных систем [1, с. 195].

В результате, рассмотрев развитие алгоритмов и способов машинной сортировки данных в массивах, можно выделить нижеследующие пять этапов. Первый этап начался в 1870 г. и продолжался до начала 1940-х гг. Его ознаменовал переход от ручной сортировки к сортировке при помощи статистических табуляторов. При этом использовался алгоритм поразрядной сортировки [10, с. 195].

Второй этап — с начала 1940-х гг. до середины 1950-х. На смену счетно-перфорационным машинам пришли ЭВМ I поколения, для которых был разработан ряд новых алгоритмов сортировки. Произошло их разделение на внешние и внутренние. Самыми популярными в данный период являлись модификации сортировки слиянием и вставками сложности O (n log n).

Третий этап начался в середине 1950-х гг. и продолжился до середины 1970-х. Для него было характерным активное развитие алгоритмов сортировки — внутренней и внешней, неустойчивой и устойчивой — многие из которых широко используются и в настоящий момент. Наибольшее число разработанных к этому времени методов относилось к обменной сортировке, сортировке путем вставок и сортировке посредством выбора [2, с. 37].

Четвертый этап продолжался с середины 1970-х до середины 1990-х гг. Появление вычислительных центров, объединяющих мощности отдельных вычислительных машин и позволяющих работать с разделением времени потребовало разработки новых алгоритмов сортировки и модификации существующих. Началось исследование задач сортировки в классе параллельных алгоритмов, были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. Одновременно происходил поиск оптимальных входных последовательностей для разных методов сортировки, что позволяло значительно сократить ее время [18, с. 73].

Пятый этап начался с середины 1990-х годов и продолжается по настоящее время. Особую актуальность получило исследование задач сортировки на частично упорядоченных множествах: задач распознавания частично упорядоченного множества М; задач сортировки частично упорядоченного множества М с использованием результатов попарных сравнений элементов, а также задач определения порядка на множестве М без априорной информации. Актуальность этих задач объясняется появлением и широким распространением компьютеров на сверхсложных микропроцессорах с параллельно-векторной структурой, а также высокоэффективных сетевых компьютерных систем [2, с. 175].

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

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

Практически каждый алгоритм сортировки можно разбить на три части:

- сравнение, определяющее упорядоченность пары элементов;

- перестановку, меняющую местами пару элементов;

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

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

Глава 2. Анализ основных алгоритмов сортировки данных

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

2.1. Сортировка вставками

На каждом шаге алгоритма выбирается один из входящих элементов и вставляется на нужную позицию в уже отсортированной части массива, алгоритм выполняется до тех пор, пока набор входных данных не будет исчерпан. Метод выбора очередного элемента из исходного массива произволен. Обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве. Приведенный ниже алгоритм использует именно эту стратегию выбора [4, с. 307].

Рисунок 1. Алгоритм сортировки вставками

Рисунок 2. Листинг алгоритма сортировки вставками

На строке 1 дано объявление функции Swap, которая выполняет перестановку двух элементов first и second в массиве array. Далее следует функция InsertionSort, реализующая сортировку вставками.

Приведённый выше алгоритм обладает следующими характеристиками:

- Высокая вычислительная сложность, необходимо сделать O(N2) сравнений и O(N2) перестановок. Если данные уже отсортированы, то необходимо сделать всего O(N) операций;

- Не требует использования дополнительной памяти (O(1));

- Устойчив;

- Прост в реализации.

2.2. Сортировка выбором

Идея алгоритма заключается в нахождении на каждой итерации минимального элемента и перемещение его на нужную позицию в уже отсортированном массиве.

Рисунок 3. Алгоритм сортировки выбором

Ниже приведена функция SelectionSort реализующая данный алгоритм.

Рисунок 4. Листинг алгоритма сортировки выбором

Сортировка вставками в данной реализации обладает следующими свойствами:

- Высокая вычислительная сложность, необходимо сделать O(N2) сравнений и O(N) перестановок

- Не требует использования дополнительной памяти (O(1));

- Неустойчива (имеются устойчивые модификации);

- Простота в реализации.

2.3. Сортировка пузырьком

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. Алгоритм имеет такое название из-за того, что на каждой итерации наименьший элемент (самый лёгкий) «всплывает» до своей позиции [4, с. 309].

Рисунок 5. Алгоритм сортировки пузырьком

Ниже дан пример реализации этого алгоритма.

Рисунок 6. Листинг алгоритма сортировки пузырьком

Сортировка пузырьком обладает следующими свойствами:

- Не требует использования дополнительной памяти (O(1));

- Устойчива;

- Простота в реализации.

2.4. Сортировка Шелла

Сортировка Шелла является усовершенствованным вариантом сортировки вставками. Идея данного метода состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Имеется большое количество модификаций, отличающихся выбором шага расстояния для каждой итерации. Ниже приведена реализация с шагом, рассчитываемым по формуле: 3ⁱ+1.

Рисунок 7. Алгоритм сортировки Шелла

Рисунок 8. Листинг алгоритма сортировки Шелла