Алгоритмы сортировки и поиска: Bubble Sort, Selection Sort и бинарный поиск

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

Пузырьковая сортировка (Bubble Sort) — самый наглядный и простой алгоритм сортировки:

• Принцип: алгоритм многократно проходит по массиву слева направо. На каждом шаге сравниваются два СОСЕДНИХ элемента: a[j] и a[j+1];

• Если левый элемент больше правого ($a[j] > a[j+1]$), они меняются местами (всплытие большего элемента в конец);

• В результате первого полного прохода самый большой элемент массива гарантированно «всплывает» на самую последнюю позицию (как пузырек воздуха в воде);

• На втором проходе второй по величине элемент встает на предпоследнее место, и так далее за $n-1$ проход массив оказывается полностью отсортирован.

Сортировка выбором (Selection Sort) работает по другому наглядному принципу:

1. На первом проходе находится минимальный элемент во всем массиве от 0 до n-1;

2. Найденный минимум меняется местами с первым элементом a[0];

3. На втором проходе ищется минимум в оставшейся неотсортированной части от 1 до n-1 и меняется местами с a[1];

4. Процесс повторяется n-1 раз.

Преимущество сортировки выбором перед пузырьковой: число перестановок (обменов) минимально и составляет ровно $O(n)$, хотя число сравнений остается квадратичным $O(n^2)$.

Поиск — это операция нахождения индекса элемента с заданным значением (ключом) в массиве.

1. Линейный поиск (Linear Search):

Последовательный просмотр всех элементов массива от первого до последнего: for x in a: if x == target: return True. Работает в любом массиве (даже неотсортированном). Время работы в худшем случае прямо пропорционально размеру массива: $O(n)$. Для массива из 1 миллиарда элементов потребуется 1 миллиард сравнений;

2. Бинарный поиск (Binary Search / Метод половинного деления):

КРИТИЧЕСКОЕ ТРЕБОВАНИЕ: массив ОБЯЗАН быть предварительно ОТСОРТИРОВАН!

Принцип «Угадай число»:

• Смотрим на центральный элемент массива mid;

• Если target == a[mid] — элемент найден!;

• Если target < a[mid] — искомое число может быть только в левой половине (правая половина отбрасывается);

• Если target > a[mid] — искомое число только в правой половине (левая половина отбрасывается);

На каждом шаге область поиска СОКРАЩАЕТСЯ ВДВОЕ!

Временная сложность бинарного поиска составляет $O(\log_2 n)$:

• Для массива из 1 000 элементов бинарный поиск найдет ответ максимум за 10 сравнений ($2^{10} = 1024$);

• Для массива из 1 000 000 элементов — всего за 20 сравнений ($2^{20} \approx 10^6$);

• Для массива из 1 000 000 000 элементов (миллиард!) — всего за 30 сравнений!

Линейный поиск для миллиарда элементов делал бы 1 миллиард операций.