ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 17
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Задачи для решения в аудитории
(сортировка)
1) Написать 4 функции порождения списка целых значений: отсортированного (по возрастанию и убыванию), случайного и почти отсортированного по возрастанию. Каждая функция принимает длину списка в качестве аргумента."
2) Реализовать функцию тестирования алгоритма сортировки. Процедура принимает на вход алгоритм сортировки и алгоритм порождения списка f_gen(list_len), генерирующий список заданной длины, количество повторений теста и список длин, использующихся для тестирования.\n",
"Для каждой длины списка функция тестирования возвращает минимальное, среднее и наибольшее количество сравнений и перестановок."
3) Реализовать модификацию сортировки пузырьком: \"камешек-пузырек\" - с чередующимися проходами, приводящими к \"всплытию\" самого большого значения списка и \"погружению\" самого маленького значения из неотсортированной части списка.
4) Добавить в сортировку счетчик количества операций перестановки и счетчик количества сравнений. Возвращать счетчики вместе с отсортированным списком.
5) Реализовать модификацию сортировки выбором на основе выбора из подсписков (описанного в лекции). Протестировать алгоритм.
6) Реализовать быструю сортировку с возможностью подсчета операций. Сравнить производительность алгоритма на случайных и упорядоченных (и почти упорядоченных) данных.
Задачи для самостоятельного решения
7) Улучшить работу быстрой сортировки на упорядоченных и почти упорядоченных за счет изменения алгоритма выбора элемента для разделения массива.
8) Реализовать эффективный алгоритм получения из большого количества отсортированных списков одного отсортированного списка."
9) Модифицировать последовательность длин шагов в сортировке Шелла
На 2[n/2k+1]+1,
"т.е. при первой сортировке будут использоваться шаги: 2*[n/4]+1, 2*[n/8]+1, ... , 3, 1 .