ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.11.2023
Просмотров: 50
Скачиваний: 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 .