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

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

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

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

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

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

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

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

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

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

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

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