Методы сортировки массивов

Сортировка массивов. Поиск элемента массива.

Лабораторная работа №8

Цель: научиться производить сортировку массивов различными способами, а также отыскивать необходимый элемент в массиве.

Теоретические сведения:

Алгоритмы поиска элемента массива.

Пусть значения элементов линейного массива 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.

Дата добавления: 2015-06-26