Алгоритмы методов сортировки и поиска.
Цель работы: «Изучить существующие алгоритмы сортировки списков (массивов) и поиска их элементов и разработать программу для реализации этих методов».
Теоретические сведения.
При работе со списками очень часто возникает необходимость перестановки элементов списка в определенном порядке. Такая задача называется сортировкой списка и для ее решения существуют различные методы. Рассмотрим некоторые из них (см. рис.7.1).
Прямые методы сортировки |
Рис.7.1 Виды прямых методов сортировки
Пример 7.1
Функция для перемены местами элементов:
void swap(int *х, int *y) {
int t = *x; /*промежуточная переменная*/
/* Перемена данных местами */
*х = *у;
*y = t;
}
1. Пузырьковая сортировка (методом обмена).
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B’=, в котором для любого 1
При обменной сортировке упорядоченный список В’ получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример 7.1
Функция BubbleSort() реализует алгоритм сортировки методом «пузырька»:
void BubbleSort(int a[],int n)
{ /*функции передается массив */
/* и его размерность */
int i, j; /* переменные цикла */
for (i=0; i
for (j=n-1; ji; j—)
if (a[j-1] a[j])
/*если элемент тяжелее следующего
swap(a[j-1],a[j]) /*поменять их местами */
}
Анализ пузырьковой сортировки.
Пузырьковая сортировка обладает несколькими характеристиками:
• После каждой итерации только один элемент данных помещается в свою правильную позицию.
• При пузырьковой сортировке сравниваются и переставляются смежные элементы данных.
• В каждой итерации внутреннего цикла выполняется не более (n-iteration-1) перестановок.
• Худший случай — когда элементы данных отсортированы в обратном порядке.
• Лучший случай — когда элементы данных уже отсортированы в правильном порядке.
• Пузырьковая сортировка легко реализуется.
Сортировка методом выбора.
Алгоритм:
- Находится наименьший элемент в массиве.
- Найденный элемент меняется с первым элементом.
- Процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее, пока в конце не останется самый большой элемент, который перемещать уже не нужно.
Пример 7.2
void MinSort(int a[], int n)
{
int i, j, k;
for (i=0; i
{
for (k=i; j=i+1; j
if (a[j] a[k]) // минимальный элемент
{
k = j; // запоминаем его номер в к
swap(a[k],a[i]);// меняем местами минимальный и
} // элем, с которого начинался цикл
}
}
Сортировка методом вставки.
Сортировка вставками — очень простой метод сортировки, при котором элементы данных используются как ключи для сравнения. Этот алгоритм сначала упорядочивает А[0] и А[1], вставляя А[1] перед А[0], если А[0] А[1]. Затем оставшиеся элементы данных по очереди вставляются в этот упорядоченный список. После k-й итерации элемент A[k] оказывается в своей правильной позиции и элементы от А[0] до A[k] уже отсортированы.
Пример 7.3
Функция InsertSort() реализует алгоритм сортировки методом вставки:
void InsertSort (int a[], int n)
{
int i, j
for (i=1; i
{ j=i;
while (a[j]=1)
{
Swap(a[j],a[j-1]);
j—; }
}
}
Анализ сортировки вставками.
Сортировка вставками обладает следующими характеристиками:
• После каждой итерации только один элемент помещается в свою правильную позицию.
• При сортировке вставками выполняется меньше перестановок, чем в пузырьковой сортировке.
• Наихудший случай — когда все элементы данных отсортированы в обратном порядке.• Наилучший случай — когда элементы почти отсортированы в правильном порядке.
• Сортировка вставками легко реализуется.