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

СОРТИРОВКА И ПОИСК В МАССИВАХ

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

Краткие теоретические сведения

При решении задач, связанных с обработкой массивов, часто возникает необходимость поиска в массиве заданного элемента.

Задача. Определить, имеется ли в массиве, содержащем n чисел, элемент, значение которого совпадает с заданным числом L. Если такой элемент существует, надо указать его порядковый номер, в противном случае напечатать сообщение об отсутствии в массиве элемента, равного L.

Решение:

Для того, чтобы найти в массиве элемент, значение которого равно заданному числу L, необходимо просматривать подряд все элементы массива, начиная с первого, и сравнивать их значения с L. Просмотр массива надо продолжать до тех пор, пока не будет найден элемент массива, равный L, или до тех пор, пока не будет просмотрен весь массив (если такого элемента не существует).

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

Сортировка – это расстановка элементов некоторого списка в заданном порядке.

Существуют разные виды сортировки (по алфавиту, по датам и т.д.), они отличаются лишь процедурой сравнения элементов. Мы рассмотрим простейший вариант сортировки – расстановку элементов массива в порядке возрастания. Программисты придумали множество методов сортировки. Они делятся на две группы:

• понятные, но не эффективные

• эффективные, но непонятные (быстрая сортировка и т.п.).

Пока мы будем изучать только методы из первой группы, которых хватает для простых задач(когда размер массива не более 1000).