Доклады о будущих и современных технологиях

ОБЗОР АЛГОРИТМОВ СОРТИРОВОК

В. А. Федюнина

Научный руководитель - Т. П. Никитина, канд. техн. наук, доцент

Ярославский государственный технический университет

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

Сортировка - это перестановка данных в соответствии с заданным об­разцом.

Методы сортировок подразделяются на два класса: внутренние (ис­пользуют в основном оперативную память) и внешние (требуют больших объёмов памяти). Сортировки можно разделить на несколько категорий: обменные, выбором, вставками, слиянием, без сравнения, гибридные и прочие.

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

В представленной работе рассматривается пять методов сортировок и даются их характеристики по выше перечисленным критериям.

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

Пирамидальная сортировка: элементы массива выстраиваются в сор­тирующее дерево. Первый (корневой) элемент всегда оказывается наи­большим и ставится на последнее место. Остальные элементы перестраи­ваются так, чтобы вновь образовалось дерево.

Сортировка Шелла: усовершенствованный вариант сортировки встав­ками. Идея метода состоит в сравнении элементов, стоящих не только ря­дом, но и на определённом расстоянии друг от друга.

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

Поразрядная сортировка: создаются пустые списки; числа упорядочи­ваются сначала по младшему разряду, затем по второму и т. д. или, наобо­рот, от старшего к младшему.