Цель лабораторной работы: освоить основные алгоритмы сортировки, написать программу с использованием этих алгоритмов.
Общие понятия
Сортировка – это процесс упорядочения элементов массива или списка по возрастанию или убыванию.
Существует много алгоритмов сортировки, отличающихся по ряду характеристик:
· Время работы, или вычислительная сложность – количество операций, затрачиваемых алгоритмом. Обычно оценивается худший сценарий, когда исходный массив оказывается максимально неупорядочен с точки зрения алгоритма.
· Затрачиваемая память (помимо исходного массива) – некоторые алгоритмы требуют выделения дополнительной памяти для временного хранения данных или формирования нового выходного массива.
Кроме того, алгоритмы можно разделить по типу доступа к данным:
· Алгоритмы внутренней сортировки применяются для сортировки данных, целиком находящихся в оперативной памяти.
· Алгоритмы внешней сортировки оперируют данными, не помещающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное количество раз.
|
|
Алгоритмы сортировки. Метод пузырька
Данный алгоритм является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная – O(n2), поэтому алгоритм эффективен только на небольших массивах данных.
Алгоритм проходит все элементы массива и попарно сравнивает их друг с другом. Если порядок сравниваемых элементов неверный, алгоритм меняет элементы местами:
// Сортировка пузырьком
void BubbleSort(ref int[] Array)
{
// Перебираем все элементы массива (кроме последнего)
for (int i = 0; i < Array.Length - 1; i++)
// Перебираем все элементы справа от i
for (int j = i + 1; j < Array.Length; j++)
// Правильный ли порядок элементов?
if (Array[i] > Array[j])
{
// Нет - меняем порядок
int t = Array[i];
Array[i] = Array[j];
Array[j] = t;
}
}