Тема № 5. Алгоритмы сортировки. Сравнительный анализ

Не делайте при помощи большего то,

что можно сделать при помощи меньшего.

(Д. Пойа)

5.1. Введение

В словарях слово "сортировка" (sorting) определяется как "распределение, отбор по сортам; деление на категории, сорта, разряды", однако, программисты обычно используют это слово в более узком смысле, обозначая им перегруппировку элементов в некотором определенном порядке. Этот процесс, пожалуй, следовало бы назвать не сортировкой, а упорядочиванием (ordering) или ранжированием (sequencing). Однако, слово сортировка уже прочно вошло в программистский "жаргон", поэтому мы будем в дальнейшем использовать слово "сортировка"в узком смысле "сортировка по порядку". Значит, теперь можно сформулировать определение "сортировка", которое будет использоваться далее.

Cортировка-это процесс перегруппировки заданного множества объектов в некотором определённом порядке.Цель сортировки- облегчить поиск элементов.

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

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

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

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

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

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

• Количество присваиваний;

• Количество сравнений;

Также важными являются такие показатели, как:

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

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

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

Все методы сортировки можно разделить на две большие группы:

• Прямые методы сортировки;

• Улучшенные методы сортировки;

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь делятся на три подгруппы:

• Сортировка простыми вставками (включением);

• Сортировка выбором (выделением);

• Сортировка обменом («пузырьковая» сортировка).

Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения метода сортировки. Прямые методы сортировки на практике используются довольно редко, так как имеют относительно низкое быстродействие. Однако они хорошо показывают суть основанных на них улучшенных методов. Кроме того, в некоторых случаях (как правило, при небольшой длине массива и/или особом исходном расположении элементов массива) некоторые из прямых методов могут даже превзойти улучшенные методы.