иДЗ политех. Лабораторная
![]()
|
ЛАБОРАТОРНАЯ РАБОТА №14 СОРТИРОВКА И ПОИСК Цель лабораторной работы: освоить основные алгоритмы сортировки, написать программу с использованием этих алгоритмов. Общие понятияСортировка – это процесс упорядочения элементов массива или списка по возрастанию или убыванию. Существует много алгоритмов сортировки, отличающихся по ряду характеристик: Время работы, или вычислительная сложность – количество операций, затрачиваемых алгоритмом. Обычно оценивается худший сценарий, когда исходный массив оказывается максимально неупорядочен с точки зрения алгоритма. Затрачиваемаяпамять(помимо исходного массива) – некоторые алгоритмы требуют выделения дополнительной памяти для временного хранения данных или формирования нового выходного массива. Кроме того, алгоритмы можно разделить по типу доступа к данным: Алгоритмы внутреннейсортировкиприменяются для сортировки данных, целиком находящихся в оперативной памяти. Алгоритмы внешнейсортировкиоперируют данными, не помещающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное количество раз. Алгоритмы сортировки. Метод пузырькаДанный алгоритм является достаточно простым и поэтому получил широкое распространение. Вычислительная сложность алгоритма квадратичная – 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; } } Сортировка выборомСортировка выбором имеет квадратичную сложность O(n2) и, как и предыдущий метод пузырька, эффективен лишь на небольших объемах данных. Алгоритм находит номер минимального значения в текущем списке, меняет этот элемент со значением первой неотсортированной позиции (если минимальный элемент не находится на данной позиции), а затем сортирует хвост списка, исключив из рассмотрения уже отсортированные элементы: // Сортировка выбором void SelectionSort(ref int[] Array) { // Перебираем все элементы массива (безпоследнего) // i – позиция первого неотсортированного элемента for (int i = 0; i < Array.Length – 1; i++) { // Позиция минимального элемента справа от i int min = i; // Перебираем все элементы справа от i for (int j = i + 1; j < Array.Length; j++) // Меньше ли очередной элемент минимального? if (Array[j] < Array[min]) // Да – теперь это минимальный элемент min = j; // Минимальный элемент не первый? // Меняем местами! if (min != i) { int t = Array[i]; Array[i] = Array[min]; Array[min] = t; } } } Быстрая сортировкаАлгоритм быстрой сортировки является одним из самых быстрых алгоритмов сортировки: в лучшем случае он имеет логарифмическую сложность, в худшем – квадратичную. Алгоритм выполняется следующим образом: Выбирается некоторый элемент, который называется опорным. Реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного – справа от него. Рекурсивно упорядочиваем массивы, лежащие слева и справа от опорного элемента. // Быстрая сортировка void QuickSort(ref int[] Array, int Left, int Right) { // i и j – индексы границ разделяемого массива int i = Left; int j = Right; // x – индекс опорного элемента int x = Array[(Left + Right) / 2]; do { // Ищем элемент слева, который больше опорного while (Array[i] < x) ++i; // Ищем элемент справа, который меньше опорного while (Array[j] > x) --j; // Если индексы не поменялись местами, // то обмениваем элементы if (i <= j) { int t = Array[i]; Array[i] = Array[j]; Array[j] = t; i++; j--; } } while (i <= j); // Рекурсивно выполняем быструю сортировку // для массивов слева и справа if (Left < j) QuickSort(ref Array, Left, j); if (i < Right) QuickSort(ref Array, i, Right); } Поиск элементаАлгоритмы поиска позволяют найти индекс элемента с требуемым значением. Если массив не упорядочен, то возможен лишь простой поиск: перебор всех элементов массива до тех пор, пока не встретится элемент с нужным значением или не закончится массив. Если элемент найден, поиск должен быть прекращён, поскольку дальнейший просмотр массива не имеет смысла: // Простой поиск элемента в массиве int IndexOf(ref int[] Array, int Value) { // Перебираем все элементы массива for (int i = 0; i < Array.Length; i++) // Нашли нужное значение? Возвращаем его индекс if (Array[i] == Value) return i; // Перебор закончился безрезультатно – возвращаем -1 return -1; } Если алгоритм поиска не нашёл подходящий элемент, он должен каким- то образом сигнализировать об этом вызывающей программе. Чаще всего в таком случае возвращается значение -1 – число, которое заведомо не может использоваться в качестве индекса массива. Вычислительная сложность алгоритма простого поиска – линейная O(n). Если массив упорядочен по возрастанию, то возможно использование дихотомического рекурсивного алгоритма: массив каждый раз делится пополам и если искомый элемент меньше среднего, то поиск продолжается в левой его половине, иначе – в правой: // Дихотомический поиск элемента в массиве static int IndexOf(ref int[] Array, int Value, int Left, int Right) { // Находим середину диапазона int x = (Left + Right) / 2; // Если нашли значение – возвращаем его индекс if (Array[x] == Value) return x; // Если середина совпадает с левой или // правой границами – значение не найдено if ((x == Left) || (x == Right)) return -1; // Продолжаем поиск слева или справа от середины if (Array[x] < Value) return IndexOf(ref Array, Value, x, Right); else return IndexOf(ref Array, Value, Left, x); } Вычислительная сложность алгоритма – логарифмическая. Индивидуальное заданиеОбщая часть задания: сформировать массив из 100 случайных чисел. Выполнить простой поиск элемента, подсчитать количество итераций. Отсортировать массив методом, указанным в своём варианте. Выполнить поиск элемента методом дихотомии, подсчитать количество итераций. Сделать выводы. Метод пузырька Сортировка выбором Быстрая сортировка |