Цель: научиться производить сортировку массивов различными способами, а также отыскивать необходимый элемент в массиве.
Теоретические сведения:
Алгоритмы поиска элемента массива. |
Пусть значения элементов линейного массива x сформированы. Требуется среди чисел x[1], x[2], …, x[n] найти такое, что x[j] = max(x[1], x[2], …, x[n]). Если в задаче требуется найти порядковый номер этого элемента, то значит необходимо найти еще и значение индекса j. Основная идея алгоритма состоит в том, что переменной max присваивается значение любого элемента массива (чаще всего первого по порядку). В случае нахождения порядкового номера переменной ind присваивается значение индекса этого элемента (т.е. 1). Далее просматриваются все элементы массива, значения которых сравниваются со значением переменной max. Если окажется, что значение какого-либо элемента массива превосходит значение переменной max, то переменная max меняет свое значение на значение большего элемента. Если поиск наибольшего элемента идет в двумерном массиве, то необходимо просматривать поочередно все элементы каждой из строк. |
Методы сортировки массивов.
|
|
1. Метод «пузырька» |
Идея метода: весь массив просматривается несколько раз, причем при каждом просмотре сравниваются значения двух соседних элементов. Если эти значения следуют не в порядке возрастания, то производится их перестановка. Так происходит до тех пор, пока не будет сделано ни одной перестановки. |
2. Метод простых обменов. |
Идея метода: весь массив просматривается несколько раз и при каждом просмотре ищется минимальный по значению элемент, который меняется местами с первым, вторым, третьим, …, предпоследним элементов массива и исключается из дальнейшего рассмотрения. |
3. Метод вставки и сдвига. |
Идея метода: делается предположение, что первые q элементов массива упорядочены, и если q+1-ый элемент меньше, чем какой-либо из первых q, то он записывается на свое место среди упорядоченных, при этом «хвост» массива «сдвигается» к концу. |
Порядок выполнения работы:
1) Запустите программу Turbo Pascal.
2) Введите массив из 10 целых чисел. Найдите элемент с минимальным значением.
3) Введите массив из 10 целых чисел и отсортируйте его в порядке возрастания и убывания элементов всеми рассмотренными методами.
4) Запишите полученные результаты в тетрадь. Оформите отчет о проделанной работе, который должен содержать тему, цель работы, формулировки задач с решениями.
5) Выйдите из программы Turbo Pascal.
Лабораторная работа №9