14. Алгоритмы сортировки

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

Сортировку массивов принято называть внутренней в отличие от сорти-

ровки файлов (списков), которую называют внешней.		Р
Для оценки эффективности сортировки часто используют следующие
критерии:		И
1. Скорость
	сортировки. Определяется числом сравнений и обменов.

	Оценивается также скорость сортировки в наилучшем и наихудшем случаях, т. к.
			У
	существуют алгоритмы, которые, имея хорошую среднюю скорость, медленно
	работают в наихудшем случае.	Г
	2. Естественность сортировки.			естественной,
		Сортировка называется
		Б

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

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

ве. Лучшими считаются алгоритмы, не перест вляющие элементы с одинако-
выми ключами.	а
Часто оценивается сложность алгоритма − зависимость объема работы,
	к
выполняемой некоторым алгоритмом, от размера входных данных.
Существует три основных способаесортировки:
1. Обмен. При так м сп собе меняются местами элементы, расположен-

ные не по порядку. Обмен пр должается до тех пор, пока все элементы не бу-
дут упорядочены.	т
2. Выбор. Вначаое щется наименьший элемент и ставится на первое ме-

	сто, затем ищется с едующий по значимости элемент и устанавливается на вто-
		и
	рое место и т. д. В резу ьтате все элементы помещаются в нужные позиции.
	3. Вставкал. Последовательно перебираются все элементы. Каждый эле-
	мент перемещается в ту позицию, где он должен стоять.
	б	14.1. Простые методы сортировки
	и
		14.1.1. Метод пузырька
	БСамый известный, самый популярный и один из самых худших алгорит-

мов сортировки (сложность алгоритма − О(n2)). Данная сортировка относится к классу обменных сортировок. Ее алгоритм содержит многократные сравнения соседних элементов и при необходимости их обмен. Элементы ведут себя подобно пузырькам воздуха в воде − каждый из них поднимается на свой уровень.

81

void s_puz(tmas a[], int n)

{

tmas t; int i, j;

for(i=1; i < n; i++) for(j=n-1; j >= i; j--) if(a[j-1].key > a[j] .key)

{			Р
t = a[j-1];
a[j-1] = a[j];
a[j] = t;
}
		И
}
В пузырьковой сортировке количество сравнений всегда одинаково неза-
висимо от изначальной упорядоченности массива.	У
14.1.2. Шейкерная сортировкаГ
Пузырьковая сортировка имеет следующую особенность: неупорядочен-
Б
ные элементы на «дальнем» конце массива з ним ют правильные положения за

один проход, а неупорядоченные элементы в н чале перемещаются на свои
места очень медленно. Для устран нияаэтой особенности можно последова-
							рки
тельно чередовать направление пров								элементов. Таким образом, сильно
						станут	на свои места. Данная модификация пу-
удаленные элементы быстро
зырьковой сортировки называе сяешейкерной сортировкой (сложность алго-
ритма − О(n2)).					о
				и
void s_shaker(tmas a[], int n)
{			л
do
	tmas t;
		б
		int i, j, k, left = 0, right = n;
{
Б	for(j=n-1; j>left; j--)
иif(a[j-1].key > a[j].key)

{

t = a[j-1]; a[j-1] = a[j]; a[j] = t;

k = j;

}

82

t = a[imin]; a[imin] = a[i]; a[i] = t;

left = k+1;

for(i=1; i < right; i++) if(a[i-1].key > a[i].key)

{

t = a[i-1]; a[i-1] = a[i]; a[i] = t;

14.1.3.Сортировка выборомБГУИР

Вмассиве выбирается элемент с наименьшима значением и меняется местами с первым элементом. Затем из остквшихся элементов находится наимень-−k = i; е

{					т
	int imin, i, j;
	tmas t;
for(i=0; i<n-1; i++)
{				о
	imin = i;
			и
for(j=i+1; j<n; j++)
		л
if (a[imin].key > a[j].key) imin = j;
	бif (imin != i)
и
Б

{

}

}

}

83