Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Для упорядочивания массивов по разным признакам (по возрастанию, по убыванию, по невозрастанию, по неубыванию и т.д.) применяют алгоритмы сортировки, при которых элементы в массиве меняют свое месторасположение в зависимости от условия сортировки. Известно большое количество алгоритмов, но в учебных целях используются наиболее простые из них.
Обменная поразрядная сортировка (сортировка “пузырьком”).
Для вектора из n элементов делается (n-1) просмотр, в каждом просмотре сравниваются попарно элементы, начиная с первого, если предыдущий элемент больше последующего, их меняют местами. После каждого просмотра очередной наибольший элемент встает на свое место (сортировка по возрастанию).
Последовательно просматриваем числа a1,...,an находим наименьшее i такое, что a i > ai+1. Поменять ai и ai+1 местами, возобновить просмотр с элемента ai+1 и т.д. Тем самым наибольшее число передвинется на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра в котором участвовали только первый и второй элементы.
Сортировка посредством выбора.
Находится минимальный элемент массива и меняется местами с первым. Среди оставшихся элементов (то есть начиная со второго) опять находится минимальный и меняется местами со вторым и процесс повторяется.
Допустим, что элементы a1,...,ai-1 уже упорядочены, тогда среди оставшихся (ai,...,an) находим минимальный элемент и меняем его местами с i-тым элементом. И т.д. пока массив не будет полностью упорядочен.
Метод простых вставок
Последовательно просматриваем a2,...,an и каждый новый элемент ai вставляем на подходящее место в уже упорядоченную совокупность a1,...,ai-1. Это место определяется последовательным сравнением ai с упорядоченными элементами a1,...,ai-1.
Метод бинарных вставок
Этот алгоритм представляет из себя оптимизированную версию предыдущего, отличие заключается в том, что при поиске место, на которое надо вставить элемент ai в уже упорядоченную совокупность a1,...,ai-1, определяется алгоритмом деления пополам (отсюда и название алгоритма "бинарные вставки" здесь понимаем как "вставка делением пополам").
Метод шелла, метод Уильяма Флойда, бинарных деревьев,…
Схема сортировки согласно алгоритму 1 (блок-схема)
MAS(исходный)
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Через нахождение минимального среди первых n элементов….
1 итерация
Просматриваем элементы с первого по десятый, находим минимальный элемент и его порядковый номер в массиве, заменяем найденным элементом первый
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Меняются местами первый элемент с восьмым
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Массив после 1 итерации
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
2 итерация
Во 2 итерации рассматриваются элементы со второго по десятый, находим минимальный элемент и его порядковый номер в массиве, заменяем найденным элементом второй
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Меняются местами второй элемент с шестым
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Массив после 2 итерации
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
……………………………………………………………
Массив после 9 итерации
MAS[1] | MAS[2] | MAS[3] | MAS[4] | MAS[5] | MAS[6] | MAS[7] | MAS[8] | MAS[9] | MAS[10] |
Далее представлены образцы блок-схем сортировки первой строки двумерного массива.
Лабораторная работа №3 (2 часа)
Тема: Составление и запись алгоритмов для вычисление суммы элементов одномерного массива, нахождение минимального элемента в виде программы. Компиляция и тестирование программы.
Цель: Приобрести навыки составления и анализа алгоритмов заполнения и обработки элементов массивов, нахождение минимального элемента в виде программы, представления их в программы, проведение компиляции и тестирования программы.
Задание: Разработатьалгоритм решения задачи представить его в виде программы на языке программирования Turbo Pascal. Провести компиляцию и тестирование программы.
Массив целых чисел размерностью 1×20 заполнить случайным образом. Вывести на экран максимальный и минимальный элементы, места их расположения, разность их значений, подсчитать количество и сумму элементов, больших 10 и меньших 40, а также среднее значение этих элементов, вывести полученные результаты.
Дата публикования: 2015-02-22; Прочитано: 482 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!