Поиск и сортировка в массивах: ОГЭ по информатике

Тема посвящена алгоритмам поиска элемента в массиве (линейный и бинарный) и сортировки массива (метод пузырька, сортировка выбором, встроенные функции). На ОГЭ проверяется умение читать и анализировать простые алгоритмы, а также писать программы на Python (или другом языке) для обработки массивов.

Что нужно знать

Массив — упорядоченная совокупность элементов одного типа, доступ по индексу (в Python индексы с 0).
Линейный поиск: последовательный перебор элементов до нахождения нужного или до конца массива. Сложность O(n).
Бинарный поиск: работает только на отсортированном массиве, делит область поиска пополам. Сложность O(log n).
Сортировка пузырьком: многократные проходы по массиву, обмен соседних элементов, если они стоят в неправильном порядке. Сложность O(n^2).
Сортировка выбором: на каждом шаге находится минимальный элемент в неотсортированной части и меняется местами с первым элементом этой части. Сложность O(n^2).
Встроенные функции сортировки (например, sorted() или list.sort() в Python) используют эффективные алгоритмы (Timsort) и не требуют ручной реализации на экзамене, если не указано иное.

Термины и понятия

Массив: структура данных, хранящая набор элементов одного типа, доступных по индексу.
Линейный поиск: алгоритм поиска, при котором элементы проверяются по порядку до нахождения искомого.
Бинарный поиск: алгоритм поиска в отсортированном массиве, при котором область поиска делится пополам на каждом шаге.
Сортировка: процесс упорядочивания элементов массива по возрастанию или убыванию.
Сортировка пузырьком: алгоритм сортировки, при котором соседние элементы меняются местами, если стоят в неправильном порядке, до полного…
Сортировка выбором: алгоритм сортировки, при котором на каждом шаге выбирается минимальный элемент из неотсортированной части и ставится на…
Сложность алгоритма (O-нотация): оценка роста числа операций при увеличении размера входных данных.

Частые ошибки

Путают индексацию: в Python первый элемент имеет индекс 0, а не 1.
При бинарном поиске забывают, что массив должен быть отсортирован.
В сортировке пузырьком неправильно задают границы внутреннего цикла (выход за пределы массива).
При поиске минимума/максимума инициализируют переменную нулём, а не первым элементом массива, что приводит к ошибке, если все элементы положительные (или отрицательные).

Как пройти тему

В курсе «Информатика» тема «Поиск и сортировка в массивах» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Начать бесплатно Открыть курс

Другие темы раздела

← Предыдущая тема: Алгоритмы обработки массивов
Следующая тема: Программирование на языке высокого уровня: базовые конструкции

Все темы: ОГЭ по информатике