Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Данные).pdf
Добавлен: 30.03.2023
Просмотров: 155
Скачиваний: 3
Введение
С тех пор, как человек изобрёл письмо и счёт, он начал делать записи обо всём, что происходит с ним и вокруг него. С появлением религиозных и государственных организаций у священников и вождей начали собираться в большом количестве записи об астрономических явлениях, об урожаях, о налогах, демографии. Одновременно появились люди, которые не только делали новые записи, но и изучали и анализировали старые. Некоторым из них удалось обнаружить благодаря накопленным записям закономерности, которые позволили предсказывать движение планет, солнечные затмения, разливы рек и прочие природные затмения.
Для того, чтобы получить из имеющихся данных какую-либо полезную информацию, для того, чтобы их было удобно анализировать необходимо сначала представить их в удобном для работы виде. Одним из видов предварительной обработки информации является её упорядочивание, сортировка, которая позволяет расставить данные по местам и увидеть, какое место они занимают.
Правильная сортировка позволяет ускорить и упростить многие последующие методы обработки данных, отбросить ошибочные данные и привлечь внимание к наиболее важным.
В этой курсовой работе сделана попытка показать эволюцию методов сортировки данных с развитием человеческой цивилизации и продемонстрированы приёмы программирования методов сортировки массивов цифровых данных.
Большая часть обработанной информации получена из Интернета. Благодаря тому, что всё больше накопленной человечеством информации оцифровывается и выставляется в свободный доступ в электронных библиотеках, необходимость в доступе к её бумажным первоисточникам возникает всё реже и труд исследователя данных, накопленных человеческой цивилизацией, становится всё более эффективным и производительным.
Глава 1. Данные
Прежде, чем рассматривать методы сортировки данных, нужно сначала разобраться с тем, что такое данные. Это понятие даже за последние 50 лет сильно изменилось и в значительной мере зависит о того, кто им пользуется и какой смысл в него вкладывает.
Например, толковый словарь Ожегова [7.] даёт такое определение данных: «1.Сведения, необходимые для какого-нибудь вывода, решения. По официальным данным. Цифровые данные. 2. Свойства, способности, качества как условия или основания для чего-нибудь. Хорошие голосовые данные. Иметь все данные для научного роста».
В толковом словаре Ушакова [8.] «данные — Сведения, обстоятельства, служащие для какого-нибудь вывода, решения. Получены данные, что здесь скрывается преступник. Нет достаточных данных для возбуждения уголовного преследования»
В экономическом словаре Райсберга и Лозовского [9.] написано следующее: «данные - 1) факты и характеризующие их числовые, количественные показатели: имена, даты событий сведения об экономических процессах, местах действия; 2) сведения, обработанные Специальным образом для принятия решений, информация».
Согласно ГОСТ 17657-79 [1.] «данные - сведения, являющиеся объектом обработки в информационных человеко-машинных системах.»
Согласно ГОСТ 15971-90 [2.] «данные - информация, представленная в виде, пригодном для обработки автоматическими средствами при возможном участии человека».
Согласно ГОСТ 34.320-96 [3.] «данные -информация, представленная в формализованном виде, пригодном для передачи, интерпретации или обработки с участием человека или автоматическими средствами».
Согласно ГОСТ Р ИСО/МЭК 12119-2000 [4.] «данные - представление информации в формализованном виде, пригодном для передачи, интерпретации или обработки.».
Согласно ГОСТ Р 52292-2004 [5.] «4.2.1 данные: Интерпретируемое формализованным способом представление информации, пригодное для коммуникации, интерпретации или обработки.».
Согласно ISO/IEC/IEEE 24765-2010 [6.] «Данные — зарегистрированная информация; представление фактов, понятий или инструкций в форме, приемлемой для общения, интерпретации, или обработки человеком или с помощью автоматических средств».
В Большом Энциклопедическим словаре [10.] написано: «данные - в информатике информация, представленная в формализованном виде, что обеспечивает возможность ее хранения, обработки и передачи…».
С точки зрения программиста данные — это часть программы, совокупность значений определённых ячеек памяти, преобразование которых осуществляет код. С точки зрения компилятора, процессора, операционной системы, это совокупность ячеек памяти, обладающих определёнными свойствами (возможность чтения и записи (необязательно), невозможность исполнения).
В этом курсовом проекте под понятием данные будет подразумеваться именно последний вариант, в соответствии с которым данные могут быть представлены как массив чисел.
Глава 2. Этапы развития методов сортировки данных
Чтобы воспользоваться эффективными алгоритмами поиска, данные должны быть упорядочены в том или ином порядке, иначе говоря, отсортированы.
Сортировка (или упорядочение), также как и поиск, является одной из часто используемых при обработке данных операций и применяется ко многим структурам данных: массивам, связным спискам, деревьям и графам.
Впервые проблема сортировки данных в больших массивах появилась в США в середине XIX века. В 1840 году там был создан центральный офис переписи населения, в который собирались данные со всех штатов. Обработка такого количества информации требовала огромных затрат труда и времени. Так, обработка данных полученных от переписи населения 1880 года потребовала привлечения сотен служащих и длилась семь с половиной лет.
В связи с этим, перед переписью 1890 года, для решения проблемы сортировки данных в очень больших массивах был проведен конкурс на лучшее электромеханическое оборудование, которое сделало бы сортировку данных более точной, быстрой и дешевой. Выиграл конкурс американский инженер-изобретатель Герман Холлерит [11.]. Он изобрел оборудование для работы с перфокартами – электронную табулирующую систему, известную как Hollerith Electric Tabulating System [12.].
Использование способа табулирования [13.] оказалось настолько эффективно, что полная обработка данных переписи 1890 года заняла всего два с половиной года, то есть в три раза меньше времени, чем при ручной обработке.
Так, в конце девятнадцатого века на смену ручной сортировки данных пришла сортировка с помощью статических табуляторов. Использовался в них алгоритм поразрядной сортировки.
Данный алгоритм представляет собой интерпретацию ключей как чисел, представленных в системе счисления с основанием R, при различных значениях R, и работающий с отдельными цифрами этих чисел. Этот метод особо удобен при сортировке данных, где ключами являются десятичные числа.
Существуют два варианта поразрядной сортировки: least significant digit (LSD) и most significant digit (MSD) [14.]. В первом случае сначала сортируются младшие разряды, а затем старшие. При этом получается следующий порядок: короткие ключи идут раньше длинных, при равном размере сортируются по алфавиту. Это необходимо для сортировки числовых данных. При MSD наоборот, сначала идет сортировка старших разрядов, потом младших. При этом получается алфавитный порядок, подходящий для сортировки строк.
Следующий этап развития методов сортировки данных начался с появлением первых электронных вычислительных машин в 1940-х.
Существуют свидетельства, что первой программой для ЭВМ с хранимой программой (с архитектурой Джона фон Неймана) была именно программа сортировки [15.].
Быстродействие ЭВМ вызвало рост интереса к новым, приспособленным к машинной обработке методам сортировки данных. В 1946 году вышла статья Джона Уильяма Мочли [16.] об алгоритмах сортировки данных. В этой статье рассматривался целый ряд новых алгоритмов сортировки, в том числе метод бинарных вставок.
До середины 1950-х годов наибольшей популярностью пользовались модификации сортировки слиянием и вставками.
В середине 1950-х, в связи с разработкой ЭВМ второго поколения, началось активное развитие алгоритмов сортировки. Основными предпосылками для этого стали разработка языков программирования высокого уровня, заметно облегчающая написание программ, увеличение доступности компьютеров, ввиду уменьшения их габаритов и стоимости, а так же увеличение производительности компьютеров до 30 тысяч операций в секунду.
В 1959 году Дональд Левис Шелл [17.Error: Reference source not found] изобрел метод сортировки с убывающим шагом. Идея этой сортировки заключается в сортировке данных находящихся на некотором расстоянии d друг от друга в несколько шагов, с сокращением этого расстояния на каждом последующем шаге. Завершается сортировка Шелла упорядочиванием элементов при d = 1.
В 1960 году Чарльз Энтони Ричард Хоар [18.] предложил метод быстрой сортировки. Несмотря на то, что эта сортировка разработана более полувека назад, она и сейчас широко применяется и является одной из самых эффективных. В этом алгоритме в массиве выбирается опорный элемент, находящийся в пределах массива, после чего происходит разделение массива на 2 части: в одной части находятся элементы меньшие, чем опорный, в другой равные или превышающие его. Для каждого полученного подмассива процедура повторяется пока в подмассиве остается 2 и более элементов. В итоге получится отсортированная последовательность.
В 1964 году Дж. У. Дж. Уильямс [19.] предложил метод пирамидальной сортировки. В алгоритме этой сортировки на каждом шаге цикла находится и устанавливается в конец массива наибольший элемент, после чего цикл продолжается без этого элемента.
Итоги этого этапа эволюции алгоритмов сортировки подвел в 1973 году Дональд Эрвин Кнут в своей фундаментальной монографии «Искусство программирования», методам сортировки и поиска он посвятил третий том своего трёхтомника [20.].
Очередной всплеск интереса к развитию алгоритмов сортировки произошел в 1970-х годах, в связи с тем, что элементной базой компьютеров стали большие интегральные схемы и появилась возможность объединения мощности нескольких вычислительных машин в единый вычислительный центр.
С середины 1970-х до 1990-х годов были достигнуты успехи в усовершенствовании уже имеющихся алгоритмов, благодаря чему заметно выросла скорость сортировки данных. Вторым направлением развития алгоритмов сортировки был поиск оптимальных входных последовательностей для разных методов сортировки, что позволяло сократить их время. Третьим направление развития было решение задачи сортировки в классе параллельных алгоритмов, для чего обобщались ранее известные парадигмы, а также разрабатывались новые алгоритмы сортировки. Развитие этого направления стимулировалось широким использованием сортирующих сетей и многомерных вычислительных решеток.
На сегодняшний день для развития методов сортировки характерно исследование задач сортировки на частично упорядоченных множествах: задач распознавания частично упорядоченного множества М; задач сортировки частично упорядоченного множества М с использованием результатов попарных сравнений элементов, а также задач определения порядка на множестве М без априорной информации. Актуальность этих задач обусловлена распространением компьютеров на сверхсложных микропроцессорах с параллельно-векторной структурой, высокоэффективных сетевых компьютерных систем.
Таким образом, в эволюции алгоритмов сортировки данных можно выделить 5 этапов.
Первый этап – с 1870 года до 1940-х годов. С ним связан переход от ручной сортировки данных, до сортировки с помощью статических табуляторов с использованием алгоритма поразрядной сортировки.
Второй этап – с начала 1940-х годов до середины 1950-х годов. На смену счетно-перфораторным машинам пришли ЭВМ первого поколения, были разработаны новые алгоритмы сортировки данных. Произошло разделение алгоритмов на внутренние и внешние.
Третий этап – с середины 1950-х годов до середины 1970-х. Для него было характерно активное развитие алгоритмов сортировки, многие из которых используются до сих пор.
Четвертый этап – с середины 1970-х годов до середины 1990-х. Модификация существующих алгоритмов развития и разработка новых связанные с появлением вычислительных центров, объединяющих мощности отдельных вычислительных машин. Начало исследования задач сортировки в классе параллельных алгоритмов.
Пятый этап – с середины 1990-х годов по настоящее время. Особую актуальность получило исследование задач сортировки на частично упорядоченных множествах.
В настоящее время с развитием вычислительной техники появились новые задачи, идёт поиск новых алгоритмов. Если раньше надо было сортировать числа, то сейчас всё чаще требуется сортировка более сложных объектов – фотографий, звуков, и им подобных. Можно считать, что сейчас наступил новый, шестой этап эволюции методов сортировки