![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Под сортировкой понимается процесс перегруппировки элементов массива, приводящий к их упорядоченному расположению относительно ключа.
Цель сортировки – облегчить последующий поиск элементов. Метод сортировки называется устойчивым, если в процессе перегруппировки относительное расположение элементов с равными ключами не изменяется. Основное условие при сортировке массивов – это не вводить дополнительных массивов, т.е. все перестановки элементов должны выполняться в исходном массиве. Сортировку массивов принято называть внутренней, а сортировку файлов – внешней.
Методы внутренней сортировки классифицируются по времени их работы. Хорошей мерой эффективности может быть число операций сравнений ключей и число пересылок (перестановок) элементов.
Прямые методы имеют небольшой код и просто программируются, быстрые, усложненные методы требуют меньшего числа действий, но эти действия обычно более сложные, чем в прямых методах, поэтому для достаточно малых значений 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)
{
Дата публикования: 2015-02-22; Прочитано: 338 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!