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

ВВЕДЕНИЕ

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

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

Эта курсовая работа состоит из двух глав: в первой будут даны основные определения понятий “сортировки” и “алгоритма”, дополненные краткими характеристиками, а также будет прослежена эволюция различных алгоритмов сортировки данных; во второй главе будут приведены конкретные примеры наиболее часто встречающихся алгоритмов сортировки данных и будут отмечены достоинства и недостатки различных методов сортировки с практической точки зрения.

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

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

Глава 1. Алгоритмы сортировки данных с теоретической точки зрения

1.1. Введение основных теоретических понятий “алгоритм”, “сортировка” и их краткие характеристики

---

Перед тем, как приступить к исследованию вопросов, касающихся алгоритмов сортировки, необходимо ввести понятие “алгоритма” и дать ему краткую характеристику.

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

По словам американского ученого в области информатики Дональда Кнута, ученые долгое время не могли найти истинное происхождение слова “алгоритм”. В своей книге “Искусство программирования”, он пишет, что “Языковеды того времени пытались объяснить его [слово “алгоритм”], комбинируя различные слова, например algiros (больной) и arithmos (число)...”^[1] Однако позже выяснилась подлинная этимология интересующего нас слова. Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, написавшего книгу “Правила восстановления и преобразования”. Он также сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем сфера употребления этого слова расширилась - оно стало применяться не только в математике. Теперь оно фактически описывает любую последовательность действий, приводящих к конечному результату, а каждое такое действие стало называться шагом алгоритма.

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

К этим свойствам относятся:

1) определенность;

2) массовость;

3) результативность;

4) дискретность.

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

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

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

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

Стоит отметить, что алгоритм может задаваться различными способами. Далее приведем распространенные формы представления алгоритма:

---

1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.

Также существуют различные виды алгоритмических структур:

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

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

Экономико-математический словарь дает следующее определение: “Сортировка данных [data sorting, ordering] — один из этапов обработки данных, упорядочение элементарных данных в последовательности, определяемой значениями некоторых признаков, называемых ключами сортировки. Например, расположение записей сортируемого массива данных по возрастанию или уменьшению значений величин, содержащихся в массиве. Сортировка массивов данных существенно ускоряет их дальнейшую обработку.”

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

1.2. Эволюция способов и алгоритмов сортировки данных в массивах

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

В статье “Эволюция способов и алгоритмов сортировки данных в массивах”, написанной Александром Дупденко, выделены основные этапы эволюции методов сортировок. Автор пишет: “Нами была поставлена цель проследить эволюцию алгоритмов сортировки данных с первых методов, используемых при машинной обработке информации, до настоящего времени, выделив основные этапы и направления их развития”.^[2]

---

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

Впервые проблема сортировки была затронута в США в середине XIX века. “В 1840 году там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В ходе переписи было опрошено 17 069 453 человек, каждая анкета состояла из 13 вопросов. Объем полученных данных был столь велик, что их обработка традиционным ручным способом потребовала непомерных затрат труда и времени. Ситуация усугублялось необходимостью проведения постоянных сверок и пересчетов из-за допускаемых при ручной сортировке данных ошибок. С каждой новой переписью, которая проводилась раз в десять лет, объем обрабатываемой информации, а вместе с ним стоимость и длительность обработки данных возрастали. Так, ручная обработка данных переписи населения 1880 года (50 189 209 человек) потребовала привлечения сотен служащих и длилась семь с половиной лет.” ^[3]
Чтобы решить проблему сортировки данных, бюро переписи был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое сделало бы сортировку данных более эффективной — более быстрой, точной и дешевой. Тогда победу одержал американский инженер Герман Холлерит (Herman Hollerith), разработавший оборудование для работы с перфокартами — электрическую табулирующую систему, которая впоследствии стала известна под названием Hollerith Electric Tabulating System.

Плюсы машины Холлерита были описаны в журнале «Вестник Опытной Физики и Элементарной Математики» в 1895 году: «Преимущества машины Голлерита заключаются:

а) в значительном ускорении и удешевлении работы. При ручном способе можно разложить и подсчитать за час не более 400 карточек. Если принять, что в Российской Империи 120 миллионов жителей, то для изготовления одной только сводной таблицы потребуется не менее … 300 000 часов… Машина сокращает работу почти в 5 раз.

б) в большей точности результатов…

в) в большей легкости получения сложных сводных таблиц… После немногих пропусках через машину всех счетных карточек получаются столь полные и разнообразные таблицы, составление которых было почти немыслимо при прежнем способе.»^[4]

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

---

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

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

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

В середине 1950-х годов с разработкой ЭВМ второго поколения началось активное развитие алгоритмов сортировки. Основными предпосылками для этого стали, во-первых, значительное упрощение и ускорение написания программ для компьютеров в результате разработки первых языков программирования высокого уровня (Фортран, Алгол, Кобол); во-вторых, значительное повышение доступности компьютеров в результате резкого уменьшения их габаритов и стоимости и, как следствие, достаточно широкое их распространение; в-третьих, увеличение производительности компьютеров до 30 тысяч операций в секунду. В 1959 году Дональд Левис Шелл (Donald Lewis Shell) предложил метод сортировки с убывающим шагом (shellsort), в 1960 году Чарльз Энтони Ричард Хоар (Charles Antony Richard Hoare) — метод быстрой сортировки (quicksort), в 1964 году Дж. У. Дж. Уильямс (J. V. J. Williams) — метод пирамидальной сортировки (heapsort). Многие из разработанных в этот период алгоритмов (например, быстрая сортировка Хоара) широко используются до настоящего времени. Итоги этого этапа активного развития алгоритмов сортировки подвел в 1973 году Дональд Эрвин Кнут (Donald Ervin Knuth) в третьем томе своей фундаментальной монографии «Искусство программирования» («The Art of Computer Programming»). К началу 1970-х годов использовались следующие виды алгоритмов внутренней сортировки: сортировка посредством подсчета; сортировка путем вставок; обменная сортировка; сортировка посредством выбора; сортировка методом слияния; сортировка методом распределения. Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок (метод простых вставок, бинарные и двухпутевые вставки, метод Шелла, вставка в список, сортировка с вычислением адреса и др.), обменной сортировке (метод пузырька и его модификации, параллельная сортировка Бэтчера, быстрая сортировка, обменная поразрядная сортировка, асимптотические методы) и сортировке посредством выбора (выбор из дерева, пирамидальная сортировка, метод исключения наибольшего из включенных, метод связанного представления приоритетных очередей). Не менее активно разрабатывались и методы внешней сортировки, в том числе методы многопутевого слияния и выбора с замещением, многофазного слияния, каскадного слияния, осциллирующей сортировки, внешней поразрядной сортировки и т. д.^[5]

---