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

Введение

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

Процессом сортировки называют действия по упорядочению некоторых данных по «ключу». Ключ сортировки – ключ, записанный в одном или нескольких полях файла. Использование ключей сортировки позволяет проводить упорядочение записей файла. Ключи могут быть разными. Например, преобразовать таблицу чисел по возрастанию или убыванию, таблицу имен - по алфавиту.

Очевидно, что с "отсортированными" данными работать легче и быстрее, чем с произвольно расположенными. Когда элементы "отсортированы", быстрее найти слово в словаре на 1000 страниц.

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

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

Глава 1. Основные понятия

Сортировка – это алгоритмический процесс перестановки объектов данного множества в определенном заданном порядке. Что же такое порядок или какое множество называется упорядоченным? Давайте дадим достаточно строгое определение:

Множество M называется упорядоченным, если между его элементами установлено некоторое отношение: a < b (a предшествует b), обладающее следующими свойствами: между любыми двумя элементами a и b существует одно и только одно из трех соотношений: a = b, a < b < a. Для любых трех элементов a, b и c из a < b < c следует a < c.

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

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

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

Время - основной параметр, характеризующий быстродействие алгоритма, называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества «А». Если на вход алгоритму подаётся множество «A», то обозначим n = |A|. Для типичного алгоритма хорошее поведение - это O(n log n) и плохое поведение - это O(n2). Идеальное поведение для упорядочения - O(n).

Память - ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы.

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

Различают некоторые свойства и классификации сортировок:

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

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

Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O(n log n), но они отличаются гибкостью применения.

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

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

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

Также алгоритмы классифицируются по:

- потребности в дополнительной памяти или её отсутствию

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

Существует множество различных методов сортировки данных. Алгоритм сортировки условно можно разбить на три основные части:

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

Глава 2. Методы сортировки данных

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

Для лучшего понимания того, в каких случаях нужно применить тот или иной алгоритм необходимо знать, что понимают под показателем сложности алгоритма. Речь идет о том, как зависит число операций, которые нужно произвести согласно алгоритму от объема данных, в нашем случае от количества элементов массива N. Сложность задачи может быть логарифмической, линейной, квадратичной, экспоненциальной и т.д., где для решения задачи необходимо выполнение O(ln(N)), O(N), O(N²) и O(e^N) операций соответственно. Например, квадратичный порядок сложности O(N²) означает, что задача может использовать N² операций, а может и 100*N², здесь коэффициент перед N² не имеет значения: важен порядок, важно знать во сколько раз программа будет работать дольше, если число N увеличится вдвое, втрое или в 10 раз. В нашем случае независимо от этого коэффициента получим, что программа будет выполняться соответственно в 4, 9 и 100 раз дольше.

Наилучшие универсальные алгоритмы сортировки имеют порядок сложности O(n*ln(n)), что позволяет в олимпиадных задачах сортировать массивы для N ~ 300 000. В качестве примера подобных алгоритмов можно привести следующие сортировки: быстрая, пирамидальная, слиянием, бинарным деревом.

Простейшие алгоритмы сортировки имеют порядок O(N²), что позволяет решать задачу с сортировкой только для N <~ 5000. Несмотря на то, что квадратичные алгоритмы дают меньший эффект, их разумно использовать, когда скоростью сортировки данных можно пренебречь, повысив скорость реализации программы. Примеры подобных сортировок: выбором, пузырьком, вставками.

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

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

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

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

Идея алгоритма очень проста. Пусть имеется массив A размером N, тогда сортировка выбором сводится к следующему:

• берем первый элемент последовательности A[i], здесь i – номер элемента, для первого i равен 1;
• находим минимальный (максимальный) элемент последовательности и запоминаем его номер в переменную k;
• если номер первого элемента и номер найденного элемента не совпадают, т. е. если k≠1, тогда два этих элемента обмениваются значениями, иначе никаких манипуляций не происходит;
• увеличиваем i на 1 и продолжаем сортировку оставшейся части массива, а именно с элемента с номером 2 по N, так как элемент A[1] уже занимает свою позицию;

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

Рассмотрим работу алгоритма на примере конкретной последовательности целых чисел. Дан массив, состоящий из пяти целых чисел 9, 1, 4, 7, 5. Требуется расположить его элементы по возрастанию, используя сортировку выбором. Начнем по порядку сравнивать элементы. Второй элемент меньше первого – запоминаем это (k=2). Далее мы видим, что он также меньше и всех остальных, а так как k≠1, меняем местами первый и второй элементы. Продолжим упорядочивание оставшейся части, пытаясь найти замену элементу со значением 9. Теперь в k будет занесена 3-ка, поскольку элемент с номером 3 имеет наименьшее значение. Как видно, k≠2, следовательно, меняем местами 2-ой и 3-ий элементы. Продолжаем расставлять на места элементы, пока на очередном шаге размер подмассива не станет равным 1-ому.

Код на С++:

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

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

Сортировка пузырьком (обменная сортировка) – простой в реализации и малоэффективный алгоритм сортировки. Метод изучается одним из первых на курсе теории алгоритмов, в то время как на практике используется очень редко.

Идея алгоритма заключается в следующем.

Соседние элементы последовательности сравниваются между собой и, в случае необходимости, меняются местами. В качестве примера рассмотрим упорядочивание методом пузырьковой сортировки массива, количество элементов N которого равно 5: 9, 1, 4, 7, 5. В итоге должен получиться массив с элементами, располагающимися в порядке возрастания их значений.

Вначале сравниваются два первых элемента последовательности: 9 и 1. Так как значение первого элемента больше значения второго, т. е. 9>1, они меняются местами. Далее сравниваются второй и третий элементы: девятка больше четверки, следовательно, элементы снова обмениваются позициями.

Аналогично алгоритм продолжает выполняться до тех пор, пока все элементы массива не окажутся на своих местах. Всего для этого потребуется N*(N-1) сравнений. В частности, на данной последовательности произведено 20 сравнений и только 5 перестановок.

Код на С++:

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