Алгоритмы сортировки и поиска — Программирование

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

Определение

Алгоритм сортировки – это метод упорядочивания элементов массива или списка по определённому правилу (обычно по возрастанию или убыванию).

Основные виды сортировок

: $\text{for } i = n - 1 \text{ до } 0 \\ \quad \text{for } j = 0 \text{ до } i - 1 \\ \quad \quad \text{if } a[j] > a[j + 1] \\ \quad \quad \text{то поменять местами} \\$

: $\min = \text{индекс минимального элемента} \\ \text{для всех } i \text{ от } 0 \text{ до } n - 1 \\ \quad \text{если элемент меньше текущего минимума} \\ \quad \quad \text{то обновляем минимум}$

: $\text{начать с индекса } 1 \\ \quad \text{пока индекс больше нуля} \\ \quad \quad \text{сравниваем текущий элемент с предыдущим} \\ \quad \quad \text{меняем их местами, если нужно}$

: $\text{выбираем опорный элемент} \\ \text{разбиваем массив на две части} \\ \text{рекурсивно сортируем каждую часть}$

Поиск в массиве

Поиск элемента в отсортированном массиве можно ускорить благодаря бинарному поиску:

$\text{left = 0, right = n - 1} \\ \text{while left <= right} \\ \ \ \text{mid = (left + right) // 2} \\ \ \ \text{if array[mid] == x} \\ \ \ \ \text{возвращаем mid} \\ \ \ \text{else if array[mid] < x} \\ \ \ \ \text{left = mid + 1} \\ \ \ \text{else} \\ \ \ \ \text{right = mid - 1}$

Сложность алгоритмов

Время выполнения

Быстрая сортировка имеет среднюю сложность $O(n \log n)$ и худшую $O(n^2)$ .
Бинарный поиск выполняется за время $O(\log n)$ .

Примеры задач

Написать программу, которая сортирует массив целых чисел методом пузырьковой сортировки.
Реализовать бинарный поиск числа в отсортированном списке.