Краткое содержание: Параграф § 8 / Информатика 11 класс

Основные сведения об одномерных массивах и их описание

В программировании используются не только простые, но и структурированные типы данных (структуры данных), примером которых являются массивы. Массив представляет собой именованную совокупность однотипных элементов, упорядоченных по индексам. В языке Pascal массив — это набор однотипных данных, фиксированное количество которых определяется при описании. Все переменные в массиве имеют одно имя, но различаются по индексу (номеру места) в массиве.

Общее описание массива в языке Pascal выглядит так: var Имя\_массива: array [Тип\_индекса] of Тип\_компонента; где «array» и «of» — служебные слова, «Тип\_индекса» — описание индексации элементов, «Тип\_компонента» — тип величин, составляющих массив.

Задачи обработки одномерных массивов

Типовые задачи, решаемые с помощью обработки одномерных массивов, включают:

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

Сортировка массива

Сортировка (упорядочение) — это один из наиболее распространенных процессов обработки данных. Под сортировкой понимают перераспределение значений элементов массива в некотором определенном порядке. Цель сортировки — ускорить последующий поиск элементов.

• Порядок неубывания (по возрастанию): каждый последующий элемент не меньше предыдущего \( ( a[i] \le a[i+1] ) \).
• Порядок невозрастания (по убыванию): каждый последующий элемент не больше предыдущего.

Рассмотрены два основных алгоритма сортировки:

• Обменная сортировка методом «пузырька»: Максимальный элемент «всплывает» («тонет») на одну позицию к началу массива за каждую итерацию. В общем случае число выполненных сравнений и обменов сопоставимо с \( n^2 \), где \( n \) — количество элементов массива.
• Сортировка выбором: На каждой итерации в несортированной части массива выбирается минимальный элемент и меняется местами с первым элементом несортированной части. Общая сложность также имеет квадратичную зависимость от \( n \). Этот алгоритм целесообразно применять, когда операция обмена элементами массива особенно трудоёмка.

Основные понятия и определения:

• Массив: Именованная, упорядоченная по индексам совокупность однотипных элементов.
• Описание массива в Pascal: var Имя\_массива: array [Тип\_индекса] of Тип\_компонента;.
• Перестановка элементов в обратном порядке: Обмен \( a[i] \) и \( a[n - i + 1] \) для \( i \) от 1 до \( n \text{ div } 2 \).
• Сортировка: Перераспределение значений элементов массива в определенном порядке (упорядочение).
• Порядок неубывания: \( a[i] \le a[i+1] \) (возрастающий порядок).
• Обменная сортировка («Пузырек»): Сортировка, при которой элементы последовательно сравниваются и обмениваются, пока максимальный элемент не «всплывет». Сложность: \( O(n^2) \).
• Сортировка выбором: На каждой итерации выбирается минимальный элемент из оставшейся части и ставится на первое место в этой части. Сложность: \( O(n^2) \).
• Типовые задачи обработки: Поиск, нахождение max/min, удаление, вставка, проверка соответствия условию.