Введение

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

• Сортировка методом пузырька (bubble);

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

• Сортировка методом вставки (insertion);

• Сортировка методом Шелла (Shell);

• Сортировка методом кучи (heap).

Это далеко не полный перечень существующих методов сортировки. Чем же объясняется такое их разнообразие? Ведь все эти методы решают одну и ту же задачу – сортировку заданного массива данных по определенному признаку. Дело здесь в такой характеристике алгоритма сортировки, как эффективность, т.е. времени, затрачиваемом этим алгоритмом на сортировку заданного массива. Она у различных методов сортировки разная. Если задать некоторый массив данных, то одни методы справятся с его сортировкой быстрее, другие – медленнее. Здесь возникает другой вопрос, – почему тогда не выбрать лучший из этих алгоритмов? Ответ прост, – потому что это невозможно. В разных условиях эти алгоритмы проявляют разную эффективность. Одни из них быстрее справляются с сортировкой одних массивов, другие – других.

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

Сравнение методов сортировки

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

• «Прямое» заполнение массива. Под прямым заполнением будем понимать такое заполнение массива, когда его элементы уже упорядочены по требуемому признаку. Фактически это означает, что алгоритму сортировки ничего не надо менять в массиве. Эффективность алгоритма сортировки в этом случае показывает, насколько быстро он может определить, что массив не нуждается в сортировке.

• «Обратное» заполнение массива. Обратное заполнение означает, что элементы массива упорядочены, но по признаку, противоположному требуемому. Например, если требуется отсортировать массив по возрастанию, обратное заполнение означает, что массив отсортирован по убыванию. Алгоритму сортировки при этом требуется переставить все элементы в обратном порядке.

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

• «Произвольное» заполнение массива означает, что элементы массива следуют в произвольном порядке. Массив не обладает никакой начальной упорядоченностью. Очевидно, что такой случай является наиболее общим.

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

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

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

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

	Прямое	Обратное	Прямое за искл. одного	Произвольное
Bubble	Высокая	Очень низкая	Высокая	Очень низкая
Exchange	Низкая	Низкая	Низкая	Низкая
Insertion	Высокая	Очень низкая	Высокая	Очень низкая
Shell	Высокая	Средняя	Высокая	Средняя
Heap	Средняя	Средняя	Средняя	Средняя

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