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

Введение

Практически в каждом программном проекте возникает необходимость обработки большого числа единообразно организованных данных. В таких случаях подобные данные удобно обрабатывать как единое целое, для чего он представляется в виде массива - формальное объединение нескольких однотипных объектов (чисел, символов, строк и т.п.) рассматриваемое как единое целое.

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

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

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

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

Внешняя сортировка оперирует запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы «видим» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью.

• доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
• объём данных не позволяет им разместиться в ОЗУ.

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

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

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

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

Глава 1 Методы сортировки массивов

Алгоритмы устойчивой сортировки (самые медленные алгоритмы сортировки, принадлежащие к классу О(n²)):

Пузырьковая сортировка (метод простых обменов).

Шейкер-сортировка.

Сортировка методом выбора (метод простого выбора).

Сортировка методом вставок.

Сортировка парным (бинарным) деревом.

Сортировка слиянием.

Методы пузырьковой сортировки, шейкер-сортировки, сортировки выбором и сортировки вставок с целью упрощения понимания будут описаны на примере сортировки колоды карт. Для этого выберем все карты одной масти из колоды, например черви, и перетасуем их (манипулирование только 13 картами позволит упростить нашу работу, сделав её более наглядной). Более подробное описание данных методов изложено в книге Джулиан М. Бакнелла: «Фундаментальные алгоритмы и структуры данных в Delphi».^[1]

1.1 Пузырьковая сортировка (метод простых обменов)

Первый алгоритм, с которыми сталкиваются все программисты при изучении азов программирования, - это пузырьковая сортировка (bubble sort).

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

Рис. 1. Один проход с помощью алгоритма пузырьковой сортировки

Пузырьковая сортировка работает следующим образом. Разложите ваши карты (помните, их всего 13). Посмотрите на двенадцатую и тринадцатую карту. Если двенадцатая карта старше тринадцатой, поменяйте их местами. То же сделайте и для пар (10, 11), (9, 10), и т.д., пока не дойдетё до первой и второй карты. После первого прохода по всей колоде туз окажется на первой позиции. Фактически когда вы «зацепились» за туз он «выплыл» на первую позицию, как показано на рисунке 1. Продолжайте процесс сортировки, уменьшая с каждым новым циклом количество просматриваемых карт и поступая так до тех пор, пока вся колода не будет отсортирована.

Идея метода: Весь массив рассматривается несколько раз, причем при каждом рассмотрении сравниваются значения 2-х соседних элементов. Если они стоят в неправильном порядке, то производится их перестановка. Так происходит до тех пор, пока не будет выполнено ни одной перестановки. Метод называют пузырьковой сортировкой, потому что меньшие значения элементов постепенно "всплывают", как пузырьки воздуха в воде, перемещаясь в начало массива, а "тяжелые" элементы "оседают на дно".

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

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

(n-1) + (n-2) + … + 1

Приведённую сумму можно упростить до n(n-1)/2 или (n^2- n)/2. Другими словами, получаем О(n²). Количество перестановок вычислить несколько сложнее, но в худшем варианте (если элементы в исходном наборе были отсортированы в обратном порядке) количество перестановок будет равно количеству сравнений, т.е. получаем О(n²).

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

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

1.2 Шейкер-сортировка

Пузырьковая сортировка имеет одну вариацию, которая на практике даёт незначительное увеличение скорости, - это так называемая шейкер-сортировка (shake sort).^[2]

Вернёмся к картам. Выполним первый проход согласно алгоритму сортировки, как показано на рисунке 2.1. Туз попадает на первую позицию.