Характеристики и классификация алгоритмов сортировки

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

Например, рассмотрим следующую последовательность записей:

<6,'E'>, <2,'B'>, <1,'A'>, <3,'C'>, <1,'D'>.

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

<1,'A'>, <1,'D'>, <2,'B'>, <3,'C'>, <6,'E'>,

в которой относительный порядок записей <1,'A'> и <1,'D'> остался без изменения. Для неустойчивого алгоритма сортировки также допустим и другой результат:

<1,'D'>, <1,'A'>, <2,'B'>, <3,'C'>, <6,'E'>,

где эти элементы поменялись местами.

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

Например, чтобы отсортировать последовательность записей вида <имя, фамилия> по фамилии, а записи с одинаковыми фамилиями - ещё и по имени, можно сначала выполнить устойчивую сортировку по имени, а затем - по фамилии:

Исходная последовательность	Последовательность после сортировки по имени	Последовательность после сортировки по фамилии
Васильев Сергей Петров Иван Васильев Иван	Петров Иван Васильев Иван Васильев Сергей	Васильев Иван Васильев Сергей Петров Иван

 

Важной характеристикой алгоритма сортировки является объём дополнительной памяти, которую он использует при своей работе. Для сортировок, которые использует не более чем константное количество дополнительной памяти, иногда используют термин “in-place”.

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

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

Имеется очень много различных алгоритмов сортировки, они используют различные идеи. Приведем примерную классификацию методов сортировки (рис. 4.1).

 

Рис.4.1. Классификация методов сортировки

В данной главе рассмотрим наиболее распространенные способы, охватив практически все направления данной классификации.

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

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

Начнем с самых простых методов.

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

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

Сортировка выбором

Одним из простейших алгоритмов сортировки является алгоритм сортировки выбором. Его суть в следующем. Пусть первые (i-1) элементов массива уже содержат правильные значения. Тогда на следующем шаге найдём в оставшейся части массива минимальный элемент и поменяем его местами с i-м – в результате правильные значения будут содержать уже i первых элементов массива.

 

		i
3	4	7	8	5	6

Рис 4.2 Иллюстрация работы сортировки выбором.

Минимальный элемент 5 меняем местами с текущим.

Приведем текст функции, выполняющей сортировку выбором:

void sort(int a[], int n)

{ for(int i=0; i<n; i++)

{//определяем индекс мин.элемента и ставим его на i-е место

int indMin=i;

for(int j=i+1; j<n; j++)

if (a[j]<a[indMin]) indMin=j;

int tmp = a[i]; a[i] = a[indMin]; a[indMin] = tmp;

}

}

Как видим, алгоритм выполняет O(n²) операций независимо от исходных данных, даже если массив изначально был отсортирован или почти отсортирован. Из-за этого недостатка он достаточно редко применяется даже для сортировки небольшого числа элементов.