СР3
.docxМИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное автономное образовательное учреждение
высшего образования
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ
ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»
Инженерная школа новых производственных технологий
Направление подготовки: 12.03.02 Оптотехника
ООП: Оптико-электронные приборы и системы
САМОСТОЯТЕЛЬНАЯ РАБОТА №3
дисциплина "Основы программирования на Python"
Выполнила:
студентка группы _________________
Проверил:
преподаватель _________________ В. Петровский
Томск - 2023
ЦЕЛЬ РАБОТЫ: обрести навыки работы с циклами и последовательностями.
ЗАДАНИЕ: реализовать следующие алгоритмы сортировки:
Сортировка выбором;
Сортировка вставками;
Сортировка “Методом пузырька”;
Сортировка Шелла;
Быстрая сортировка.
Программа должна сгенерировать список случайных неотсортированных чисел и вывести его на экран.
Затем этот список должен быть отсортирован каждым из пяти перечисленных выше алгоритмов сортировки. Необходимо также зафиксировать время работы каждого алгоритма сортировки и при выводе отсортированного массива на экран выводить время его сортировки.
ХОД РАБОТЫ
generate_random_list(size): принимает параметр size, который определяет размер генерируемого списка. Возвращает список случайных целых чисел от 1 до 1000 запрашиваемого размера.
Сортировка выбором (selection_sort). Осуществляется поиск наименьшего элемента в неотсортированной части списка и обмен его с первым элементом неотсортированной части. Время начала и окончания сортировки фиксируется для измерения продолжительности сортировки.
Сортировка вставками (insertion_sort). Внешний цикл проходит по элементам списка, начиная со второго элемента. Текущий элемент сохраняется в переменной value. Внутренний цикл сравнивает value с предыдущими элементами и сдвигает их вправо, пока не будет найдено место для вставки value. После завершения внутреннего цикла, value вставляется на найденное место.
Сортировка методом пузырька (bubble_sort). Внешний цикл проходит по элементам списка от первого до предпоследнего. Внутренний цикл сравнивает текущий элемент с его соседом справа и меняет их местами, если текущий элемент больше следующего. После каждого прохода внутреннего цикла наибольший элемент "всплывает" в конец списка. Повторяется до тех пор, пока весь список не будет отсортирован.
Сортировка Шелла (shell_sort). Внешний цикл определяет размер шага, начиная с половины длины списка, и уменьшает его вдвое на каждой итерации. Внутренний цикл проходит по элементам списка, начиная с gap-го элемента. Элементы сравниваются и меняются местами, если необходимо. После завершения внутреннего цикла, шаг gap уменьшается вдвое. Повторяется до тех пор, пока шаг не станет равным 1.
Быстрая сортировка (quick_sort). Если длина списка больше 1, выбирается случайный элемент x из списка. Создаются три новых списка: low - содержит элементы меньше x, eq - содержит элементы равные x и hi - содержит элементы больше x. Рекурсивно вызывается quick_sort для списков low и hi. Возвращается объединение отсортированных списков low, eq и hi.
РЕЗУЛЬТАТЫ:
Таким образом, в данной работе была реализована программа, которая представляет реализацию нескольких алгоритмов сортировки: сортировки выбором, сортировки вставками, сортировки методом пузырька, сортировки Шелла и быстрой сортировки.
Также были приобретены навыки работы с понимание различных алгоритмов сортировки, умение реализовывать алгоритмы сортировки на языке программирования, понимание использования встроенных функций и модулей для генерации случайных чисел, знание работы с временем выполнения программы, умение использовать рекурсию для реализации алгоритма быстрой сортировки.