Файл: Методы сортировки данных: эволюция и сравнительный анализ. Примеры использования (Общие представления о методах сортировки).pdf

Введение

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

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

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

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

Программирование содержит ряд важных внутренних задач. Одной из важнейших задач программирования является задача сортировки.

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

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

Помимо общего научного интереса к алгоритмам сортировки, в каждом алгоритме интересно оценить его так называемую сложность.

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

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

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

Также важны такие показатели, как:

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

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

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

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

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

В этой курсовой работе мы обсудим эффективность различных методов сортировки данных.

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

Целью исследования было сравнение преимуществ и недостатков наиболее распространенных алгоритмов сортировки данных.

Для достижения этой цели были поставлены и решены следующие задачи:

1. Рассмотрим наиболее распространенные алгоритмы сортировки данных;

2. Выявить достоинства и недостатки этих алгоритмов;

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

1. Общие представления о методах сортировки

В словарях слово «сортировка» определяется как «распределение, отбор по сортам; При делении на категории, оценки, категории программисты обычно используют это слово в более узком смысле, обозначая им перестановку элементов в определенном порядке. Этот процесс, возможно, следует называть не сортировкой, а упорядочением или ранжированием (сегментированием) [4]. Однако слово «сортировка» уже прочно вошло в повседневную жизнь программистов, поэтому мы будем продолжать использовать слово «сортировка» в узком смысле слова «сортировка по порядку». Теперь сформулируем определение «сортировка», которое мы будем использовать в будущем.

Сортировка - это процесс перегруппировки заданного набора объектов в определенном порядке.

Целью сортировки является облегчение поиска элементов в отсортированном наборе. В этом смысле сортирующие элементы присутствуют практически во всех задачах. Упорядоченные объекты содержатся в различных утверждениях, в каталогах, в телефонных книгах, в оглавлениях, в библиотеках, в словарях, на складах и почти везде, где их нужно искать [5].

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

Зависимость выбора алгоритмов от структуры данных настолько сильна, что методы сортировки обычно делятся на две категории: сортировка массивов и сортировка (последовательных) файлов. Эти два класса часто называют внутренней и внешней сортировкой [1].

2. Эволюция методов сортировки

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

Перед переписью 1890 года для решения проблемы сортировки данных по очень большим объемам информации по инициативе бюро переписей был проведен конкурс на лучшее электромеханическое сортировочное оборудование, которое сделало бы сортировку данных более эффективной - быстрее, точнее и дешевле. В конкурсе победил американский инженер и изобретатель немецкого происхождения Херман Холлерит, который разработал оборудование для перфокарт - электрическую систему табулирования, которая стала известной как система электронных табло Hollerith. Использование этого оборудования в ходе переписей США в 1890 и 1900 годах считалось очень успешным.

Вот как преимущества машины Холлерита были описаны в российском журнале «Вестник экспериментальной физики и элементарной математики» в 1895 году: «Преимущества машины Холлерита:

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

б) более точные результаты ...

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

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

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

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

В середине 1950-х годов, с развитием компьютеров второго поколения, началась активная разработка алгоритмов сортировки. Основными предпосылками для этого были, во-первых, значительное упрощение и ускорение написания программ для компьютеров в результате разработки первых языков программирования высокого уровня (Fortran, Algol, Kobol); во-вторых, значительное увеличение доступности компьютеров в результате резкого уменьшения их размеров и стоимости и, как следствие, их довольно широкого распространения; в-третьих, увеличение производительности компьютера до 30 тыс. операций в секунду.

В 1959 году Дональд Льюис Шелл предложил метод сортировки по убыванию (шеллсорт), в 1960 году - метод быстрой сортировки Чарльз Энтони Ричард Хоар (быстрая сортировка), а в 1964 году - метод Дж. У. Дж. Уильямса, метод heapsort. Многие алгоритмы, разработанные в этот период (например, быстрая сортировка Хоара), широко использовались до настоящего времени [4]. Результаты этого этапа активной разработки алгоритмов сортировки были обобщены в 1973 году Дональдом Эрвином Кнутом в третьем томе его фундаментальной монографии «Искусство программирования».

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

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

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

Еще один всплеск интереса к алгоритмам сортировки произошел в середине 1970-х годов, когда крупные интегральные схемы стали элементной базой компьютеров, и стало возможным объединить мощь компьютеров, создав единые вычислительные центры, позволяющие работать с разделением времени [3].

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