Файл: Алгоритмы сортировки данных (Основные понятие алгоритмов сортировки).pdf

Введение

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

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

Объектом исследования в данной работе являются основные понятия алгоритмов сортировки, предметом исследования – конкретные алгоритмы.

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

Задачами данной работы являются:

• определение понятия алгоритма сортировки данных;
• рассмотрение характеристик оценки алгоритмов сортировки данных;
• изучение свойств и классификации алгоритмов сортировки;
• рассмотрение конкретных примеров алгоритмов сортировки данных в соответствии с классификацией устойчивых и неустойчивых алгоритмов.

Основной данного исследования послужили работы таких авторов, как Таненбаум, Паттерсон и Хеннеси.

1. Основные понятие алгоритмов сортировки

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

Алгоритм является набором инструкций, которые описывают порядок действий исполнителя с целью достижения определенного результата. В старой трактовке использовалось слово «последовательность» вместо слова «порядок», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, в том числе и параллельно, при условии, что это позволяют используемые исполнители^[1].

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

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

• закон трихотомии, при котором ключ одного элемента может быть только больше, меньше или равен ключу другого элемента;
• транзитивность, при которой если ключ одного элемента, больше ключа второго элемента, который в свою очередь больше ключа третьего элемента, то ключ первого элемента должен быть больше ключа третьего элемента^[3].

Задачей сортировки по неубыванию является нахождение перестановки элементов, при которой ключи располагаются в порядке неубывания:

Аналогично можно определить сортировку по невозрастанию^[4] [2, 5, 6].

1.2. Оценка алгоритма сортировки

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

Время является основным параметром, который характеризует быстродействие алгоритма. Данный параметр также называется вычислительной сложностью. С целью упорядочения важны лучшее, среднее и худшее поведения алгоритма в терминах мощности входного множества. Для типичного алгоритма выделяют хорошее поведение и плохое поведение. Также существует идеальное поведение для упорядочения. Использующие только абстрактную операцию сравнения ключей алгоритмы сортировки всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана, который использует тот факт, что пространство ключей ограничено. Данный алгоритм чрезвычайно сложен, и не применим в повседневной практике. Также существует понятие сортирующих сетей, предполагающие возможность одновременного (например, при параллельном вычислении) проведения несколько сравнений^[5].

Ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Обычно данные алгоритмы требуют определенное количество памяти. При оценке не учитывается место, занимаемое исходным массивом, и независящие от входной последовательности затраты, например, на хранение кода программы. Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте^[6] [3, 7].

1.3. Свойства и классификация алгоритмов сортировки

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

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

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

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

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

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

Также алгоритмы классифицируются по потребности в дополнительной памяти или ее отсутствию и потребности в знаниях о структуре данных, которые выходят за рамки операции сравнения, или отсутствию таковой^[10] [2, 3].

2. Конкретные примеры алгоритмов сортировки

2.1. Алгоритмы устойчивой сортировки

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

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

Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка^[11].

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на свое место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива. Таким образом, элемент «всплывает» до нужной позиции, как пузырек в воде, отсюда и название алгоритма^[12] [3, 7].

2.1.2. Шейкерная сортировка

Шейкерная сортировка также называется сортировко2 перемешиванием или двунаправленной. Данный вид сортировки является разновидностью пузырьковой сортировки. Анализируя метод пузырьковой сортировки, можно отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения^[13].

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

Эти две идеи приводят к следующим модификациям в методе пузырьковой сортировки. Границы рабочей части массива (то есть части массива, в которой происходит движение) устанавливаются в месте последнего обмена на каждой итерации. Массив просматривается поочередно слева направо и справа налево^[14] [4, 5].

2.1.3. Сортировка вставками

Сортировка вставками является алгоритмом сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов^[15].

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

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

2.1.4. Гномья сортировка

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

Концептуально алгоритм прост и не требует вложенных циклов. На практике алгоритм может работать так же быстро, как и сортировка вставками^[17].

Алгоритм находит первое место, где два соседних элемента стоят в неправильном порядке и меняет их местами. Он пользуется тем фактом, что обмен может породить новую пару, стоящую в неправильном порядке, только до или после переставленных элементов. Он не допускает, что элементы после текущей позиции отсортированы, таким образом, нужно только проверить позицию до переставленных элементов [4, 6]^[18].