Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №16. Составление алгоритма сортировки в неупорядоченном массивеЦель работы: Получение навыков построения алгоритмов с использованием пузырьковой сортировки. Сортировка применяется во всех без исключения областях программирования, будь то базы данных или математические программы. Практически каждый алгоритм сортировки можно разбить на три части: - сравнение, определяющее упорядоченность пары элементов; - перестановку, меняющую местами пару элементов; - собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, сока все элементы множества не будут упорядочены. Пузырьковая сортировка Самый простой алгоритм этой группы получил название пузырьковой сортировки. Не самый удачный алгоритм. Заключается в сравнении соседних элементов и, при необходимости их перестановке. При неубывающем упорядочении элементы "выплывают" как пузырьки каждый до своего уровня. Описание алгоритма: Используется два цикла. Внешний проходит N-1 раз, это гарантирует, что даже в худшем случае каждый элемент будет находиться на своем месте. Исходный массив d, c, a, b. В процессе работы программы массив будет изменяться следующим образом:  Расположим цифровой массив 4, 9, 7, 6, 2, 3 сверху вниз, от нулевого элемента - к последнему. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.  После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию... Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.  Теоретический материал для повторения Массив представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива. Доступ к каждому элементу массива осуществляется с помощью индекса – в общем случае порядкового номера элемента в массиве. Массивы могут быть как одномерными (адрес каждого элемента определяется значением одного индекса), так и многомерными (адрес каждого элемента определяется значением нескольких индексов). Массивы занимают смежные ячейки памяти. (Другими словами, элементы массива в памяти расположены последовательно друг за другом.) Ячейка с наименьшим адресом относится к первому элементу массива, а с наибольшим — к последнему. Предположим, мы используем массив a из семи элементов. После заполнения массив будет выглядеть следующим образом.
Для работы с одномерными массивами применяются циклические алгоритмы. Алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим. Тело цикла - это повторяющаяся последовательность действий (блок инструкций). Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Цикл называется арифметическим, если число повторений цикла известно заранее или может быть вычислено. Выражение 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) Составьте алгоритм, упорядочивающий элементы массива, стоящие на нечетных местах, в возрастающем порядке, а на четных - в убывающем. 2) В неупорядоченном массиве могут быть совпадающие элементы. Из каждой группы одинаковых элементов оставить только один, удалив остальные и «поджав» массив к его началу. 3) В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить). |