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

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

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

Методы внутренней сортировки классифицируются по времени их работы. Хорошей мерой эффективности может быть число операций сравнений ключей и число пересылок (перестановок) элементов.

Прямые методы имеют небольшой код и просто программируются, быстрые, усложненные методы требуют меньшего числа действий, но эти действия обычно более сложные, чем в прямых методах, поэтому для достаточно малых значений n (n £ 50) прямые методы работают быстрее. Значительное преимущество быстрых методов начинает проявляться при n ³ 100.

Среди простых методов наиболее популярны следующие.

1. Метод прямого обмена (пузырьковая сортировка):

for (i = 0; i < n–1; i++)

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

if (a[i].key > a[j].key) { // Переставляем элементы

r = a[i]; a[i] = a[j]; a[j] = r;

}

Функция сортировки элементов целочисленного динамического массива а размера n может иметь следующий вид:

void Sort_Puz(int *a, int n)

{