Реализация алгоритмов выбора на языке Python
Алгоритмы выбора (selection) на Python
Как найти k-й наименьший элемент в массиве за ожидаемое линейное время?
Алгоритм Quickselect (выбор Хоара) - это эффективный метод, основанный на разделении массива как в быстрой сортировке. Он выбирает опорный элемент (pivot) и перераспределяет элементы так, что все меньшие оказываются слева, а большие - справа. Если индекс опоры равен k, то элемент найден. Иначе алгоритм рекурсивно выполняется в соответствующей части.
Пример реализации с рандомизированным выбором опоры:
import random
def quickselect(arr, k):
if len(arr) == 1:
return arr[0]
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k < len(left):
return quickselect(left, k)
elif k < len(left) + len(mid):
return mid[0]
else:
return quickselect(right, k - len(left) - len(mid))алгоритмы и структуры данных python (алгоритмы и структуры данных в python)
>>> arr = [3, 7, 1, 9, 4, 6, 8] >>> quickselect(arr, 2) # 2-й наименьший (индексация с 0) 3
примеры линейных алгоритмов на python (примеры линейных алгоритмов на python)
class="fw-bold" Пояснение шагов:
- Функция получает массив и индекс k (0-индексация).
- Случайный выбор опоры предотвращает вырожденные случаи.
- Формируются три списка: left, mid, right.
- Если k меньше числа элементов слева, рекурсия уходит в left.
- Если k попадает в середину, возвращается значение опоры.
- Иначе рекурсия в right с уменьшенным k.
Временная сложность: в среднем O(n), в худшем O(n²) (если неудачно выбирать опору).
Типичные ошибки:
- Забыть скорректировать k при рекурсии в правую часть.
- Использовать сортировку вместо разделения - теряется эффективность.
- Не обрабатывать случай пустого массива или выхода k за границы.
Решение: всегда проверять длину массива и корректировать k = k - len(left) - len(mid).
Как найти k-й элемент с помощью полной сортировки массива?
Самый простой способ - отсортировать массив и взять элемент по индексу k. В Python используется метод sort() или функция sorted().
def selection_sort(arr, k):
arr_sorted = sorted(arr)
return arr_sorted[k]динамическое программирование python (решение задач динамического программирования на python)
>>> selection_sort([5, 3, 8, 1, 9], 2) 5
типы алгоритмов в python (типы алгоритмов в python)
Временная сложность O(n log n), что медленнее для больших массивов, но код прост и понятен. Подходит для небольших данных или однократных операций.
Проблема: неэффективно при больших n и если нужно только одно значение.
Как найти k-й наименьший элемент, используя кучу (heap)?
Можно применить max-кучу размера k для поиска k-го наименьшего. Проходим по массиву, поддерживая кучу из k наибольших элементов из просмотренных. В конце корень кучи - искомый элемент.
import heapq
def selection_heap(arr, k):
heap = []
for x in arr:
heapq.heappush(heap, -x) # max-куча через отрицание
if len(heap) > k:
heapq.heappop(heap)
return -heap[0]алгоритм выбора python (алгоритм выбора (selection) на python)
>>> selection_heap([4, 2, 9, 1, 7], 3) 4
алгоритм евклида на python (алгоритм евклида на python)
Временная сложность O(n log k). Если k мало, алгоритм эффективен. Минус: не позволяет найти k-й наибольший напрямую (нужна min-куча).
Ошибка: забыть, что heapq реализует min-кучу, для max-кучи нужно отрицание.
Как гарантировать линейное время в худшем случае? (Алгоритм медианы медиан)
Алгоритм BFPRT (Blum–Floyd–Pratt–Rivest–Tarjan) находит медиану медиан в качестве опоры, что даёт гарантированное O(n). Разделение на группы по 5 элементов, рекурсивное нахождение медианы среди медиан.
def median_of_medians(arr, k):
if len(arr) <= 5:
return sorted(arr)[k]
groups = [sorted(arr[i:i+5]) for i in range(0, len(arr), 5)]
medians = [group[len(group)//2] for group in groups]
pivot = median_of_medians(medians, len(medians)//2)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
if k < len(left):
return median_of_medians(left, k)
elif k < len(left) + len(mid):
return mid[0]
else:
return median_of_medians(right, k - len(left) - len(mid))квадраты python (вычисление квадратов чисел в python)
Алгоритм сложен для понимания, но гарантирует O(n). Используется редко в повседневных задачах из-за константы и сложности реализации.
Типичная ошибка: неправильно выбрать группы 3 или 7 - гарантия линейного времени только для групп размера 5 (нечётное число).
Как найти k-й наибольший элемент, используя те же алгоритмы?
Достаточно преобразовать задачу: для k-го наибольшего (1-индексация) используем индекс n-k в отсортированном массиве, или модифицируем условие в quickselect, меняя знаки сравнения. Также можно искать через min-кучу размера k.
def quickselect_max(arr, k):
# ищем k-й наибольший (k с 1)
n = len(arr)
return quickselect(arr, n - k) # переиспользуем функцию для наименьшегомаксимальная сумма python (максимальная сумма)
>>> quickselect_max([1, 5, 8, 3, 9], 2) # 2-й наибольший = 8 8
Важно: k-й наибольший = (n-k)-й наименьший при 0-индексации.
Расширенные примеры алгоритмов выбора
Итеративная версия Quickselect (без рекурсии)
Рекурсия может быть заменена циклом для экономии стека. Используем два указателя left и right, постепенно сужая диапазон поиска.
def quickselect_iterative(arr, k):
left = 0
right = len(arr) - 1
while left <= right:
pivot_idx = partition(arr, left, right)
if pivot_idx == k:
return arr[pivot_idx]
elif k < pivot_idx:
right = pivot_idx - 1
else:
left = pivot_idx + 1
def partition(arr, left, right):
pivot = arr[right]
i = left
for j in range(left, right):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[right] = arr[right], arr[i]
return i
arr = [3, 1, 9, 2, 7]
print(quickselect_iterative(arr, 2)) # 33
Пояснение: partition разбивает массив относительно последнего элемента. Итерация продолжается, пока не достигнут нужный индекс.
Поиск k наименьших элементов без изменения порядка исходного массива
Используем кучу (max-heap) размера k. При проходе по массиву добавляем элемент, если куча переполняется - удаляем наибольший. В итоге в куче останутся k наименьших, упорядоченных по убыванию.
import heapq
def k_smallest_elements(arr, k):
heap = []
for x in arr:
heapq.heappush(heap, -x)
if len(heap) > k:
heapq.heappop(heap)
return sorted([-x for x in heap]) # возвращаем в порядке возрастания
result = k_smallest_elements([10, 2, 8, 1, 6, 3], 3)
print(result) # [1, 2, 3][1, 2, 3]
Обработка больших потоков данных: можно не хранить весь массив, а обрабатывать элементы один за другим.
Поиск k-й порядковой статистики с помощью NumPy (для численных задач)
Библиотека NumPy имеет встроенную функцию `numpy.partition`, которая частично сортирует массив и возвращает k-й элемент. Это быстрее ручных реализаций на больших данных.
import numpy as np
arr = np.array([7, 2, 1, 9, 5, 4])
k = 2 # индекс 2 (0-база)
result = np.partition(arr, k)[k]
print(result) # 44
Примечание: `np.partition` не гарантирует порядок остальных элементов, только то, что все элементы до k не больше его, а после - не меньше. Это соответствует идее quickselect.
Рандомизированный выбор опоры с помощью выборки из трех (median-of-three)
Чтобы уменьшить вероятность наихудшего случая в quickselect, можно выбирать опору как медиану первого, среднего и последнего элемента. Такой подход часто используется на практике.
def quickselect_median3(arr, k):
def select(l, r, k):
if l == r:
return arr[l]
pivot = median_of_three(arr, l, r)
p_idx = partition_around(arr, l, r, pivot)
if k == p_idx:
return arr[p_idx]
elif k < p_idx:
return select(l, p_idx - 1, k)
else:
return select(p_idx + 1, r, k)
return select(0, len(arr) - 1, k)
def median_of_three(arr, l, r):
m = (l + r) // 2
# упорядочить l, m, r по значению
if arr[l] > arr[m]:
arr[l], arr[m] = arr[m], arr[l]
if arr[l] > arr[r]:
arr[l], arr[r] = arr[r], arr[l]
if arr[m] > arr[r]:
arr[m], arr[r] = arr[r], arr[m]
return arr[m]
def partition_around(arr, l, r, pivot):
# перемещаем опору в конец
p_idx = arr.index(pivot, l, r+1)
arr[p_idx], arr[r] = arr[r], arr[p_idx]
i = l
for j in range(l, r):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[r] = arr[r], arr[i]
return i
print(quickselect_median3([5, 1, 8, 3, 9], 2)) # 55
Данный метод улучшает асимптотику на практических данных, хотя в худшем случае всё равно O(n²) при специально подобранных входных данных.
Использование встроенной функции statistics.median для поиска медианы
Если нужно найти медиану (частный случай k = n/2), можно воспользоваться модулем statistics.
import statistics
arr = [1, 5, 2, 8, 3]
med = statistics.median(arr)
print(med) # 3.03.0
Внутри statistics.median использует сортировку, но для небольших массивов это удобно.