Информатика и технология программирования


Задания к лабораторным работам


Алгоритм сортировки реализовать в виде функции, возвращающей в качестве результата характеристику трудоемкости алгоритма (например, количество сравнений ). Если имеется базовый алгоритм сортировки (для Шелла - " пузырек" , для Шейкер - " пузырек" , для вставки с двоичным поиском - погружение), то аналогично оформить базовый алгоритм и произвести сравнение эффективности.



1. Сортировка вставками, место помещения очередного элемента в отсортированную часть производить с помощью двоичного поиска. Двоичный поиск оформить в виде отдельной функции.



2. Сортировка Шелла. Частичную сортировку с заданным шагом, начиная с заданного элемента оформить в виде функции. Алгоритм частичной сортировки - вставка погружением.



3. Сортировка разделением. Способ разделения : вычислить среднее арифметическое всех элементов массива и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).



4. Шейкер-сортировка. Процесс движения в прямом и обратном направлении реализовать в виде одного цикла, используя параметр - направление движения (+1/-1) и меняя местами нижнюю и верхнюю границы просмотра.



5. "Быстрая" сортировка с итерационным циклом вычисления медианы. Для заданного интервала массива, в котором производится разделение, ищется медиана обычным способом. Затем выбирается та часть интервала между границей и медианой, в которой находится середина исходного интервала, и процесс повторяется.



6. Сортировка циклическим слиянием с использованием одного выходного и двух входных массивов. Для упрощения алгоритма и разграничения сливаемых групп в последовательности в качестве разделителя добавить " очень большое значение" ( MAXINT) .



7. Сортировка разделением. Способ разделения : интервал между минимальным и максимальным значениями элементов массива разбить пополам и относительно этого значения разбить массив на две части (с использованием вспомогательных массивов).



8. Простое однократное слияние. Разделить массив на n частей и отсортировать их произвольным методом.


Начало  Назад  Вперед