Файл: Методы сортировки данных и ее эволюции.pdf

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

Задачи работы:

Рассмотрет эволюцию сортировки данных;

Изучить методы сортировки данных;

Провести сравнение алгоритмов сортировки.

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

ГЛАВА 1. ИСТОРИЯ И ХАРАКТЕРИСТИКА СОРТИРОВКИ ДАННЫХ

1.1.Эволюция сортировки данных

Важное практическое значение проблема сортировки данных в больших массивах впервые приобрела в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, куда стекались первичные данные из всех штатов. В ходе переписи было опрошено 17 069 453 человек, каждая анкета состояла из 13 вопросов. Объем полученных данных был столь велик, что их обработка традиционным ручным способом потребовала непомерных затрат труда и времени. Ситуация усугублялось необходимостью проведения постоянных сверок и пересчетов из-за допускаемых при ручной сортировке данных ошибок. С каждой новой переписью, которая проводилась раз в десять лет, объем обрабатываемой информации, а вместе с ним стоимость и длительность обработки данных возрастали. Так, ручная обработка данных переписи населения 1880 года (50 189 209 человек) потребовала привлечения сотен служащих и длилась семь с половиной лет [1].

Перед переписью 1890 года для решения проблемы сортировки данных в очень больших массивах информации по инициативе бюро переписи был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое сделало бы сортировку данных более эффективной — более быстрой, точной и дешевой. Конкурс выиграл американский инженер и изобретатель немецкого происхождения Герман Холлерит (Herman Hollerith), разработавший оборудование для работы с перфокартами — электрическую табулирующую систему, ставшую известной как Hollerith Electric Tabulating System. Использование этого оборудования при переписях населения США в 1890 и 1900 годах было признано очень успешным. Вот как были описаны преимущества машины Холлерита в русском журнале «Вестник Опытной Физики и Элементарной Математики» в 1895 году: «Преимущества машины Голлерита заключаются: а) в значительном ускорении и удешевлении работы. При ручном способе можно разложить и подсчитать за час не более 400 карточек. [4]

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

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

Итоги этого этапа активного развития алгоритмов сортировки подвел в 1973 году Дональд Эрвин Кнут (Donald Ervin Knuth) в третьем томе своей фундаментальной монографии «Искусство программирования» («The Art of Computer Programming»). К началу 1970-х годов использовались следующие виды алгоритмов внутренней сортировки: сортировка посредством подсчета; сортировка путем вставок; обменная сортировка; сортировка посредством выбора; сортировка методом слияния; сортировка методом распределения. Наибольшее количество разработанных к тому времени методов относилось к сортировке путем вставок (метод простых вставок, бинарные и двухпутевые вставки, метод Шелла, вставка в список, сортировка с вычислением адреса и др.), обменной сортировке (метод пузырька и его модификации, параллельная сортировка Бэтчера, быстрая сортировка, обменная поразрядная сортировка, асимптотические методы) и сортировке посредством выбора (выбор из дерева, пирамидальная сортировка, метод исключения наибольшего из включенных, метод связанного представления приоритетных очередей). [11]

Не менее активно разрабатывались и методы внешней сортировки, в том числе методы многопутевого слияния и выбора с замещением, многофазного слияния, каскадного слияния, осциллирующей сортировки, внешней поразрядной сортировки и т. д. [4]. Очередной всплеск интереса к алгоритмам сортировки произошел в середине 1970-х годов, когда элементной базой компьютеров стали большие интегральные схемы и появилась возможность объединения мощности вычислительных машин путем создания единых вычислительных центров, позволяющих работать с разделением времени. В период с середины 1970-х до 1990-х годов были достигнуты значительные успехи в увеличении скорости сортировки за счет повышения эффективности уже известных к тому времени алгоритмов путем их доработки или комбинирования. К примеру, нидерландский учёный Эдсгер Вибе Дейкстра (Edsger Wybe Dijkstra) в 1981 году предложил алгоритм плавной сортировки (Smoothsort), который является развитием пирамидальной сортировки (Heapsort). Вторым направлением совершенствования алгоритмов сортировки стал поиск оптимальных входных последовательностей для разных методов сортировки, что позволяло значительно сократить ее время. Третьим направлением, наиболее интенсивно развивающимся, было решение задачи сортировки в классе параллельных алгоритмов, для чего не только обобщались ранее известные парадигмы, но и разрабатывались принципиально новые алгоритмы. Развитие данного направления стимулировалось и все более широким использованием сортирующих сетей, а также многомерных вычислительных решеток.

Таким образом, исследовав эволюцию способов и алгоритмов машинной сортировки данных в массивах, можно выделить следующие пять этапов. Первый этап начался в 1870 году и длился до начала 1940-х годов. Его ознаменовал переход от ручной сортировки к сортировке с помощью статистических табуляторов. При этом использовался алгоритм поразрядной сортировки. Второй этап — с начала 1940-х годов до середины 1950-х. На смену счетно-перфорационным машинам пришли ЭВМ первого поколения, для которых был разработан ряд новых алгоритмов сортировки. [15]

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

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

1.2 Методы сортировки данных

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

typedef double real;

typedef unsigned long ulong;

typedef unsigned short ushort;

typedef unsigned char uchar;

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

Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. [2]

Будем строить готовую последовательность, начиная с левого конца массива. Алгоритм состоит из n последовательных шагов, начиная от нулевого и заканчивая (n-1)-м.

На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

Вне зависимости от номера текущего шага i, последовательность a[0]...a[i] (выделена курсивом) является упорядоченной. Таким образом, на (n-1)-м шаге вся последовательность, кроме a[n] оказывается отсортированной, а a[n] стоит на последнем месте по праву: все меньшие элементы уже ушли влево.

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

Расположим массив сверху вниз, от нулевого элемента - к последнему.

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