Алгоритмы и анализ сложности. Лабораторная Блок-схемы. лаб1. Лабораторная работа 1 Описание и свойства алгоритмов Выбрать два метода сортировки сложности O(n 2 )
 Скачать 156.16 Kb.
|
|
Лабораторная работа №1 Описание и свойства алгоритмов Выбрать два метода сортировки сложности O(n2); Выполнить словесно-формульное описание алгоритмов; Нарисовать блок-схемы алгоритмов; Показать соответствие описанных алгоритмов основным свойствам алгоритмов. Сортировка пузырьком – простой алгоритм сортировки. Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N -1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде, отсюда и название алгоритма).  Сортировка выбором (selection sort) В неотсортированном подмассиве ищется локальный максимум (минимум). Найденный максимум (минимум) меняется местами с последним (первым) элементом в подмассиве. Если в массиве остались неотсортированные подмассивы — повторяем.  Сортировка вставками (Insertion Sort) На каждой итерации программа берет один из элементов и подыскивает для него место в уже отсортированном списке. Так происходит до тех пор, пока не останется ни одного неиспользованного элемента. То есть программа рассматривает каждый элемент и вставляет его на нужное место.  Показать соответствие описанных алгоритмов основным свойствам алгоритмов: Основные свойства алгоритмов Дискретность(дискретна структура) - Процесс решения задачи по алгоритму разбит на отдельные действия Конечность - Каждое из действий и весь алгоритм в целом обязательно завершаются (за конечное число шагов). Определенность(детерминированность) - Правила и порядок выполнения действий алгоритма имеют единственное толкование. Результативность(сходимость) - По завершении выполнения алгоритма обязательно получается конечный результат. Массовость - Применимость алгоритма к различным наборам исходных данных. Понятность(доступность) - Все действия должны быть понятны исполнителю, то есть должны принадлежать системе действий данного исполнителя. |