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

Введение

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

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

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

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

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

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

В основу исследования легли книги по архитектуре персональных компьютеров из серии «Классика Computer Science» всемирно известных авторов, таких как Э. Таненбаум, Д. Паттерсон и Д. Хеннесси.

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

Паттерсон является заслуженным профессором Калифорнийского университета в Беркли, работающим в области микропроцессоров и информатики. Он известен своим вкладом в проектирование RISC-процессоров и создание принципа работы RAID-массивов.

Хеннесси является американским ученым, работающим в области микропроцессоров и информатики. Также он является основателем MIPS Computer Systems Inc. и ректором Стэнфордского университета.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Внешняя сортировка оперирует запоминающими устройствами большого объема, но с последовательным доступом, а не с произвольным, то есть в конкретный момент виден единственный элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Данная методика накладывает дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, которые обычно используют дополнительное дисковое пространство. Также доступ к данным во внешней памяти производится намного медленнее операций с оперативной памятью. Доступ к носителю осуществляется последовательным образом так, что в каждый момент времени можно записать или считать только один следующий за текущим элемент. Объем данных не позволяет им разместиться в оперативном запоминающем устройстве^[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].

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