Методические указания по выполнению лабораторных и практических работ по мдк
 Скачать 3.25 Mb.
|
|
Практическая работа № 1.7. Оценка сложности алгоритмов сортировки Цель работы: получение навыков определения сложности алгоритмов сортировки. Теоретический материал Алгоритм сортировки 38 Алгоритм сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. Оценка алгоритма сортировки Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти: Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = | A | . Для типичного алгоритма хорошее поведение — это [1] и плохое поведение — это . Идеальное поведение для упорядочения — . Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью , использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за операций. При этом число n должно быть заранее известно; Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет ). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте. Классификация алгоритмов сортировки Устойчивость (stability) — устойчивая сортировка не меняет взаимного расположения равных элементов. Естественность поведения — эффективность метода при обработке уже упорядоченных, или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет , но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы. Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два: Внутренняя сортировка оперирует с массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте, без дополнительных затрат. o В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки. Внешняя сортировка оперирует с запоминающими устройствами большого объёма, но с доступом не произвольным, а последовательным (упорядочение файлов), т. е. в данный момент мы 'видим' только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным на носителе производится намного медленнее, чем операции с оперативной памятью. o Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. o Объём данных не позволяет им разместиться в ОЗУ. 39 Также алгоритмы классифицируются по: потребности в дополнительной памяти или её отсутствии потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствии таковой Задание № 1 Напишите программу, которая выполняет следующие функции: – Генерацию элементов массива с заданной размерностью; – Сортировку массива каждым из 6 способов (пузырьковая сортировка, сортировка вставкой, сортировка выбором, быстрая сортировка, сортировка слиянием, шейкерная сортировка); – Осуществляет подсчет времени сортировки и количества перестановок. Задание № 2 Провести эксперимент сортировки массива со следующим количеством элементов: 1'000, 10'000 и 100'000. Для проведения эксперимента необходимо произвести по 5 запусков каждого алгоритма и выбрать наилучшее время. Выбранный наилучший результат занести в таблицу. Сортировку осуществлять с одним и тем же набором данных. Таблица 1. Результаты эксперимента. Вид сортировки 1'000 10'000 100'000 Время Количество перестановок Время Количество перестановок Время Количество перестановок Bubble sort 0.003 76564 0.32 967782 33.389 9887983 Selection sort 0.002 990 0.256 9950 34.215 99509 Insertion sort 0.003 251411 0.375 25021276 40.468 1800935483 Quick sort 0.000 2733 0.001 41167 0.017 574566 Merge sort 0.001 9976 0.016 133616 0.237 1668928 Shaker sort 0.005 239124 0.76 24972810 82.974 1802548963 Задание № 3 Оцените сложность каждого алгоритма и сделайте вывод о наилучшем способе сортировки массива по каждой размерности массива. Свой ответ поясните. С начала хотелось бы кратко описать каждый из представленных алгоритмов: Сортировка пузырьком (от англ. Bubble sort) – данный алгоритм меняет местами два соседних элемента, если первый элемент массива больше второго. Так происходит до тех пор, пока алгоритм не обменяет местами все неотсортированные элементы. Сложность настоящего алгоритма равно 𝑂(𝑛 2 ). Сортировка выбором (от англ. Selection sort) – суть алгоритма заключается в проходе по массиву от начала до конца в поиске наименьшего элемента массива и перемещении его в начало. Сложность настоящего алгоритма равно 𝑂(𝑛 2 ). Сортировка вставками (от англ. Insertion sort) – алгоритм сортирует массив по мере прохождения по его элементам. На каждой итерации берется элемент и сравнивается с каждым элементом в уже отсортированной части массива, таким образом находя «свое место», после чего элемент вставляется на свою позицию. Так происходит до тех пор, пока алгоритм не пройдет по всему массиву. На выходе получается отсортированный массив. Сложность настоящего алгоритма равно 𝑂(𝑛 2 ). Быстрая сортировка (от англ. Quick sort) – суть алгоритма заключается в разделении массива на два под-массива, средней линией считается элемент, который находится в самом центре массива. В ходе работы алгоритма элементы, меньшие чем средний будут перемещены в лево, а большие в право. Такое же действие будет происходить рекурсивно и с под-массива, они будут разделяться на еще два под-массива до тех пор, пока не будет чего разделать (останется один элемент). На выходе получается отсортированный массив. Среднее значение настоящего алгоритма равно 𝑂(𝑛 × log 𝑛). Сортировка слиянием (от англ. Merge sort) – этот алгоритм упорядочивает списки (или другие структуры данных, доступ к элементам, которых можно получать только последовательно) в определенном порядке. Слияние означает объединение двух и более 40 последовательностей в одну упорядоченную последовательность при помощи циклического выбора элементов, доступных в данный момент. Сначала задача разбивается на несколько подзадач меньшего размера. Затем эти задачи решаются с помощью рекурсивного вызова или непосредственно, если их размер достаточно мал. Затем их решения комбинируются, в результате чего массив упорядочивается. Среднее значение настоящего алгоритма равно 𝑂(𝑛 × log 𝑛). Шейкерная сортировка (от англ. Cocktail sort) – она же сортировка перемешиванием, она же двунаправленная сортировка – по сути всего лишь оптимизированный алгоритм сортировки пузырьком (см. выше). В ее основе также лежит сравнение двух соседних элементов. Единственное отличие состоит в том, что теперь это происходит в двух направлениях поочередно, постепенно сужая диапазон сортировки. В итоге за один проход в конец массива «всплывает» наибольший элемент из диапазона, а за следующий проход – в начало массива наименьший (при сортировке по возрастанию). Эти элементы можно больше не рассматривать и таким образом диапазон сужается с двух сторон. Шейкерная сортировка работает быстрее, чем сортировка пузырьком, но все еще имеет сложность 𝑂(𝑛 2 ). Оценить сложность алгоритмов нагляднее всего можно в виде таблицы и графика (для сравнения в ней представлены также некоторые другие виды сортировок): Таблица 2. Сравнение временной сложности алгоритмов сортировки. Выводы: в результате проведенного эксперимента выяснилось, что наиболее эффективным из представленных алгоритмов является быстрая сортировка, которая полностью оправдывает свое название. Имея незначительную разницу во времени при упорядочивании небольших массивов (до 1 ' 000 элементов), она проявляет весь свой потенциал при работе с большими массивами данных (свыше 10 ' 000 элементов), что является ключевым преимуществом при работе в крупных проектах. Сортировка слиянием при упорядочивании небольших массивов (до 1 ' 000 элементов) демонстрирует хорошие показатели, однако при сортировке массивов среднего и большого объема (свыше 10 ' 000 элементов) она показывает неудовлетворительные результаты. Сортировки пузырьком, выбором и вставками имеют схожие алгоритмы работы и показывают неудовлетворительные результаты с массивами любой разрядности. Самым медленным способом сортировки является шейкерная. Она показывает худшие результаты в массивах любой размерности и к работе с коммерческими проектами категорически не допускается. Задание Оформите отчет, который должен содержать: – Описание алгоритмов сортировки в виде блок-схемы и ее описанием; – Реализацию этих алгоритмов на языке программирования C++; 41 – Описание компьютера на котором проводился эксперимент (вид процессора, тактовая частота, количество ядер, количество оперативной памяти и т. д.); – Результаты эксперимента в виде таблицы; – Вывод по каждой размерности массива с указанием лучшей сортировки и пояснениями. Практическая работа № 1.8. Оценка сложности алгоритмов поиска Цель работы: Получение навыков построения алгоритмов с использованием пузырьковой сортировки. Теоретический материал Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Практически каждый алгоритм сортировки можно разбить на три части: сравнение, определяющее упорядоченность пары элементов; перестановку, меняющую местами пару элементов; собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. Пузырьковая сортировка Самый простой алгоритм этой группы получил название пузырьковой сортировки. Не самый удачный алгоритм. Заключается в сравнении соседних элементов и, при необходимости их перестановке. При неубывающем упорядочении элементы "выплывают" как пузырьки каждый до своего уровня. Ход работы Описание алгоритма: Используется два цикла. Внешний проходит N-1 раз, это гарантирует, что даже в худшем случае каждый элемент будет находиться на своем месте. Исходный массив d, c, a, b. В процессе работы программы массив будет изменяться следующим образом: Расположим цифровой массив 4, 9, 7, 6, 2, 3 сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами. После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию. Массив представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива. Доступ к каждому элементу массива осуществляется с помощью индекса – в общем случае порядкового номера элемента в массиве. Массивы могут быть как одномерными (адрес каждого элемента определяется значением одного индекса), так и многомерными (адрес каждого элемента определяется значением нескольких индексов). Массивы занимают смежные ячейки памяти. (Другими словами, элементы массива в памяти расположены последовательно друг за другом.) Ячейка с наименьшим адресом относится к первому элементу массива , а с наибольшим — к последнему. Предположим, мы используем массив a из семи элементов. После заполнения массив будет выглядеть следующим образом. a[0] a[1] a[2] a[3] a[4] a[5] a[6] 42 5 1 2 4 6 3 9 Для работы с одномерными массивами применяются циклические алгоритмы. Алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим. Тело цикла - это повторяющаяся последовательность действий (блок инструкций). Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Выражение 1 выполняется только один раз в начале цикла. Обычно оно определяет начальное значение параметра цикла (инициализирует параметр цикла). Выражение 2 — это условие выполнения цикла. Выражение 3 обычно определяет изменение параметра цикла. Блок инструкций — тело цикла, то есть инструкции, которые должны выполняться заданное количество раз.. Обратите внимание на то, что после вычисления выражения 3 происходит возврат к вычислению выражения 2 — проверке условия повторения цикла. Пример Заполнить массив десятью значениями 30,53,11,35,17,42,21,84,75,61. Отсортировать данную последовательность методом выбора. Чтобы не загромождать блок-схему, вывод исходного и отсортированного массивов обозначен одним блоком «вывод» (надо помнить, что для вывода на экран массива используется цикл с параметром). Результат работы алгоритма: Исходный массив: 30 53 11 35 17 42 21 84 75 61 11 30 53 17 35 21 42 61 84 75 11 17 30 53 21 35 42 61 75 84 11 17 21 30 53 35 42 61 75 84 11 17 21 30 35 53 42 61 75 84 11 17 21 30 35 42 53 61 75 84 11 17 21 30 35 42 53 61 75 84 11 17 21 30 35 42 53 61 75 84 11 17 21 30 35 42 53 61 75 84 11 17 21 30 35 42 53 61 75 84 **********Отсортированный массив 11 17 21 30 35 42 53 61 75 84 Задание Составить блок-схему алгоритма решения задачи. 1) Изменить процедуру сортировки так, чтобы сортировка производилась по убыванию элементов. 2) Проверить, является ли данная последовательность целых чисел упорядоченной по убыванию. Если нет, упорядочить ее. 3) Отсортировать четные элементы массива с помощью пузырьковой сортировки. Дополнительные задания 1) Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в 43 возрастающем порядке, а на четных - в убывающем. 2) В неупорядоченном массиве могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один , удалив остальные и «поджав» массив к его началу. 3) В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить). Практическая работа № 1.9. Оценка сложности рекурсивных алгоритмов Цель работы: получение навыков построения алгоритмов с использованием рекурсии. Теоретический материал При создании программы для решения сложной задачи программист обычно разбивает ее на подзадачи, чтобы для каждой такой подзадачи написать подпрограмму, а затем объединить все написанные подпрограммы в программу. Если подзадача достаточно сложная, то для решения может оказаться полезным разбить ее еще на более мелкие подзадачи и программировать каждую из них отдельно и т. д. Блок-схема предопределенного процесса – обращение к подзадаче (в С++ к функции): Рассмотрим задачу вычисления факториала числа N! = 1.2.3. . .N. Результатом будет одно число, поэтому лучше алгоритм оформить в виде функции. Ее блок-схема показана на рисунке. Переменная К используется для накопления произведения и, поскольку 0! = 1 и1! = 1, то в блоке 2 ей сразу присваивается значение 1. Далее, если N>1, то в цикле, образованном блоками 4-5, накапливается искомое произведение и помещается в переменную К. В блоке 6 имя Fact функции получает значение вычисленного произведения из ячейки К. Для процедур действия, размещенного в блоке 6, не может быть, а для функций оно должно быть обязательно, поскольку иначе значение функции на выходе окажется неопределенным. Обращение к функции в других алгоритмах (головных, процедурах, функциях) производится по ее имени. При этом оно может входить в состав выражений. В качестве фактических параметров могут быть использованы как переменные, константы, так и целые выражения. Важно только, чтобы фактический параметр был совместим по типу с формальным, который содержится в заголовке описания алгоритма. Пример использования функции Fact показан на рисунке. В операторе присваивания используется обращение к функции для N = 6. После передачи этого значения в алгоритм и вычислений внутри него результат будет сначала присвоен имени функции, т. е. переменной Fact, а затем в операторе присваивания - переменной L. Часто бывает, что в процессе такого разбиения задача сводится к самой себе. Если при этом исходные данные становятся проще, то этот процесс можно продолжать до тех пор, пока исходные данные не окажутся настолько простыми, что решение задачи для них станет тривиальным. Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Никакого парадокса здесь нет – компьютер лишь последовательно выполняет встретившиеся ему в программе команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать. void Rec(int a){ if (a>0)Rec(a-1); cout<<"\n a="< } 44 Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). void main(){clrscr(); int x; cout<<"\nx=";cin>>x; Rec(x); getch(); } Ниже представлена блок-схема, показывающая последовательность выполнения операторов. Результат работы программы: /* x=3 a=0 a=1 a=2 a=3 */ Процедура Rec вызывается с параметром a = 3. В ней содержится вызов процедуры Rec с параметром a = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр a = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии. Четвертая вызванная процедура (Rec(0)) напечатает число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел: 0, 1, 2, 3. Еще один визуальный образ происходящего представлен на рисунке. Выполнение процедуры Rec с параметром 3 состоит из выполнения процедуры Rec с параметром 2 и печати числа 3. В свою очередь выполнение процедуры Rec с параметром 2 состоит из выполнения процедуры Rec с параметром 1 и печати числа 2. И т. д. Пример Опишем рекурсивную функцию вычисления факториала. В функции один параметр — натуральное число п. Тривиальный случай — это вычисление значения 1!. Заметим, что верно следующее соотношение п! = п х (п — 1)!, поэтому можно свести задачу вычисления п! к решению той же задачи, но с другим, более "простым" параметром. //rec03 //рекурсия вычисление факториала 45 #include #include long fact(int n) { int f; if (n==1) f=1; else f=n*fact(n-1); return f; } void main(){ clrscr(); int a; cout<<"a="; cin>>a; cout<<"\n Factorial="< getch(); } /* a=7 Factorial=5040 */ Пусть n=3. Как будет выполняться вызов fact(n) ? На рисунке представлена схема выполнения вызова функции. Стрелки указывают порядок вычисления. Сначала происходит движение по стрелкам вниз, указывающее на то, что происходит временное прерывание выполнения текущего вызова, и переход к выполнению вызова более низкого уровня, пока не будет получен тривиальный случай. Затем происходит подъем вверх, что означает возобновление прерванных вызовов. Первым возобновится выполнение такого вызова, который был прерван последним. Схема выполнения вызова рекурсивной функции |