Алгоритмы сортировки и поиска

dlyachainikov.ru · Программирование

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

Пузырьковая сортировка: $\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}$

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

Пузырьковая сортировка:

\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}