§ 20. Использование библиотечных функций для сортировки и поиска данных
Site: | Профильное обучение |
Course: | Информатика. 10 класс (Повышенный уровень) |
Book: | § 20. Использование библиотечных функций для сортировки и поиска данных |
Printed by: | Guest user |
Date: | Tuesday, 10 December 2024, 11:34 AM |
Многие из рассмотренных нами задач достаточно часто встречаются на практике. Поэтому их решения, оформленные в виде соответствующих функций, были включены в библиотеку algorithm[1]. Для подключения библиотеки необходима команда #include <algorithm>.
Рассмотрим некоторые из функций этой библиотеки. В Приложении можно найти более подробный список.
20.1. Линейный поиск элемента
Для организации линейного поиска элемента в массиве можно использовать следующие функции:
У всех этих функций три параметра. Первые два параметра являются итераторами, которые определяют диапазон для поиска в массиве, третий задает условие поиска. При этом левая граница диапазона входит в область поиска, а правая — нет. То есть диапазон поиска является полуинтервалом. Если поиск осуществляется во всем векторе, то используются итераторы begin() и end(). В качестве результата функции find и find_if выдают значение итератора, указывающего на первый элемент, соответствующий поисковому запросу. Компаратор для функций, реализующих поиск элемента в диапазоне, имеет один параметр. Компаратор возвращает значение true, если элемент удовлетворяет условию поиска, и false, если нет. Функция поиска передает в компаратор поочередно значения из диапазона поиска. Как только для какого-то значения получили true, работа поисковой функции прекращается. Если элемент не найден, функция возвращает итератор на правую границу области поиска. Пример 20.1. Дан линейный массив целых чисел. Написать программу, которая: 1) найдет позицию элемента, равного x; 2) найдет позицию элемента, кратного x; 3) посчитает количество элементов, равных x; 4) посчитает количество элементов, кратных x. Этапы выполнения задания I. Исходные данные: переменные n — количество чисел в массиве, a — массив. II. Результат: позиции элементов n1 и n2 (пункты 1 и 2) и количество элементов k1 и k2 (пункты 3 и 4). III. Алгоритм решения задачи. 1. Ввод исходных данных. Данные сгенерируем случайным образом. 2.1. find для пункта 1. 3. Вывод результата. IV. Описание переменных: n, k1, k2, n1, n2, x – int, a – vector<int>. Функции min_element и max_element возвращают итератор на минимальное и максимальное значения элементов в диапазоне. Пример 20.2. Дан линейный массив целых чисел. Написать программу, которая найдет минимальный и максимальный элементы в массиве. Этапы выполнения задания I. Исходные данные: переменные n — количество чисел в массиве, a — массив. II. Результат: позиции минимального и максимального элементов nmin и nmax и их значения. III. Алгоритм решения задачи. 1. Ввод исходных данных. Данные сгенерируем случайным образом. |
V. Программа:
VI. Тестирование. Анализ результатов. Индекс числа 3 в массиве равен 1, а также это число кратно самому себе. В массиве одно число, равное 3, и два числа (3 и 18), кратных 3. Обратите внимание на то, что переменная x описана как глобальная переменная, поскольку она используется как в функции main, так и в компараторе comp. V. Программа:
VI. Тестирование. Функции min_element и max_element могут иметь третий параметр — компаратор, определяющий правило порядка для элементов указанного диапазона. |
20.2. Сортировка
Для сортировки элементов вектора используется функция sort, которая имеет два параметра: границы сортируемого диапазона. Если в качестве границ диапазона использовать стандартные итераторы begin() и end(), то элементы вектора будут отсортированы в порядке возрастания. Если использовать итераторы rbegin() и rend(), то элементы будут отсортированы в порядке убывания. При этом вектор должен состоять из элементов, для которых определены операции сравнения: целых или вещественных чисел, символов, строк. Если вектор состоит из элементов, для которых не определено понятие порядка (структур или других векторов), то для их сортировки необходим третий параметр — функция-компаратор, которая задает отношения порядка для элементов. Пример 20.3. Дан линейный массив целых чисел. Написать программу, которая отсортирует числа в порядке убывания. Этапы выполнения задания I. Исходные данные: переменные n — количество чисел в массиве, a — массив. II. Результат: отсортированный массив. III. Алгоритм решения задачи. 1. Ввод исходных данных. Данные сгенерируем случайным образом. IV. Описание переменных: n – int, a – vector<int>. Для сортировки в порядке убывания можно воспользоваться стандартным компаратором, который задает порядок — большее раньше меньшего: sort(v.begin(), v.end(), greater<int>()); Кроме компаратора greater, могут использоваться компараторы: less (меньше), equal_to (равно), not_equal_to (не равно), less_equal (меньше либо равно), greater_equal (больше либо равно). Эти компараторы ассоциированы с типом своего параметра, для которого должны быть определены операции сравнения. По умолчанию работает компаратор less, который можно опускать. Пример 20.4. На плоскости заданы своими координатами n точек. Расположить точки в порядке возрастания их абсцисс. Найти все пары соседних точек, абсциссы которых находятся на расстоянии не меньше l друг от друга. Этапы выполнения задания I. Исходные данные: переменные n — количество точек в массиве, l — расстояние, a — массив. II. Результат: отсортированный массив. III. Алгоритм решения задачи. 1. Ввод исходных данных. |
В реализации Стандартной библиотеки шаблонов (STL) в C++ для реализации сортировки используется подход Дэвида Мюссера. В 1997 г. он предложил использовать интроспективную сортировку (Introsort). Это комбинированный алгоритм сортировки, который использует быструю сортировку и переключается на пирамидальную[1] сортировку, когда глубина рекурсии превысит логарифм от числа сортируемых элементов. В быстрой сортировке выбор опорного элемента производится как медианы из трех. Когда количество элементов становится меньше 16, применяется алгоритм сортировки простыми вставками. Таким образом, функция sort объединяет в себе три алгоритма сортировки: быструю, пирамидальную и сортировку простыми вставками. Функция гарантировано использует порядка операций сравнений и обменов. V. Программа:
VI. Тестирование. V. Программа:
VI. Тестирование. [1] Пирамидальная сортировка использует бинарное сортирующее дерево для хранения данных. Почитать о ней можно здесь: Кормен, Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн., 3-е издание. — М.: «Вильямс», 2013. |
20.3. Бинарный поиск
Если массив отсортирован, то для поиска элемента x можно применять алгоритм бинарного поиска. Алгоритм дихотомии реализован в нескольких функциях:
В качестве параметров задаются итераторы, указывающие диапазон поиска и искомое значение. Функции могут иметь четвертый параметр — компаратор, указывающий на порядок сортировки элементов в массиве. Пример 20.5. Дан линейный отсортированный массив целых чисел. Написать программу, которая получит количество элементов, меньших x и больших y. Массив упорядочен в порядке убывания. Данные прочитать из файла. Числа x и y ввести с клавиатуры. Этапы выполнения задания I. Исходные данные: переменные n –количество чисел в массиве, a — массив, числа x и y. II. Результат: количество элементов, меньших x и больших y. III. Алгоритм решения задачи. 1. Ввод исходных данных. 2.1. Для поиска n1 — номера первого значения, меньшего x, воспользуемся функцией upper_bound. |
Функция equal_range возвращает диапазон, содержащий все элементы, равные x. Диапазон определяется двумя итераторами, первый указывает на первый элемент, не меньший (равный или больше), чем x, второй указывает на первый элемент, больший, чем x. Первый итератор может быть получен использованием lower_bound(), второй — upper_bound(). Возвращаемым значением является тип пара (pair), содержащий два итератора. Для использования типа данных pair необходима библиотека utility. V. Программа:
VI. Тестирование. Анализ результатов. Значение 7 – номер первого меньшего 88, а значение 8 — номер первого большего 82. |
Вопросы к параграфу
1. Какую библиотеку можно использовать для поиска и сортировки элементов массива? 2. Какие функции позволяют осуществлять поиск элемента? 3. С помощью какой функции можно отсортировать массив? 4. В каких функциях реализован алгоритм бинарного поиска? |
Упражнения
1. Реализуйте решение задач из упражнений 5—7 после § 12, используя функции поиска из библиотеки algorithm.
2. Используя функции для поиска минимального и максимального элементов, реализуйте решение задач из упражнений 6—7, 9—16 после § 13.
3. Отсортируйте массивы из упражнений 3—5 после § 18, используя функцию sort.
4. Используя функции бинарного поиска из библиотеки algorithm, реализуйте решения задач из упражнений 1—2 после § 19.
5. На плоскости своими координатами заданы n точек. Расположить точки в порядке убывания их абсцисс. Найти все тройки соседних точек, абсциссы которых строго убывают.
6*. На плоскости своими координатами заданы n точек. Расположить точки в порядке возрастания угла наклона вектора, заданного данной точкой (угол между вектором и ось ОХ). Если углы равны (отличаются не более чем на 0.00001), то сортировать по длине вектора. Найти величину максимального угла между соседними векторами.