Примеры алгоритмов Python для решения сложных задач
Примеры алгоритмов сортировки и поиска на Python
Как реализовать быструю сортировку с минимальным использованием дополнительной памяти?
Быстрая сортировка (Quick Sort) является одним из самых эффективных алгоритмов для сортировки массивов. Представленная версия выполняет сортировку на месте, не создавая дополнительные списки. Основная идея заключается в выборе опорного элемента и разделении массива на части относительно него.
def quicksort_inplace(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quicksort_inplace(arr, low, pivot_index - 1)
quicksort_inplace(arr, pivot_index + 1, high)
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1алгоритм задачи python (алгоритмы задач на python)
Шаги: выбираем последний элемент как опорный (pivot), затем проходим по массиву, помещая элементы меньше или равные pivot слева, а больше – справа. После прохода pivot оказывается на правильной позиции. Рекурсивно повторяем для левой и правой частей.
Как реализовать сортировку слиянием (Merge Sort) для стабильной сортировки?
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return resultпроверка на простое число python (проверка числа на простоту в python (алгоритм))
Сортировка слиянием гарантирует O(n log n) в худшем случае и является стабильной. Алгоритм делит массив пополам, рекурсивно сортирует каждую половину и затем сливает их в упорядоченный результат.
Как работает встроенная сортировка Python (Timsort) и когда её использовать?
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
arr.sort() # in-place
sorted_arr = sorted(arr) # возвращает новый списокPython алгоритмы языка (алгоритмы в python)
Timsort – гибридный алгоритм, объединяющий сортировку слиянием и вставками. Он оптимизирован для реальных данных, часто встречающихся на практике (частично упорядоченные массивы). В большинстве случаев его использование является оптимальным выбором.
Как реализовать бинарный поиск (Binary Search) в отсортированном массиве?
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1Бинарный поиск работает за O(log n) и требует предварительно отсортированного массива. Алгоритм сравнивает искомое значение со средним элементом и сужает область поиска в два раза на каждом шаге.
Расширенные примеры нестандартных алгоритмов на Python
Сортировка подсчётом (Counting Sort) для целых чисел с ограниченным диапазоном
def counting_sort(arr, max_val):
count = [0] * (max_val + 1)
for num in arr:
count[num] += 1
sorted_arr = []
for i in range(max_val + 1):
sorted_arr.extend([i] * count[i])
return sorted_arr
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr, 8))[1, 2, 2, 3, 3, 4, 8]
Алгоритм использует дополнительный массив счётчиков, что эффективно при малом разбросе значений. Временная сложность – O(n + k), где k – диапазон значений. Не подходит для данных с большим разбросом или нецелочисленных.
Сортировка кучей (Heap Sort) с явным построением кучи
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
arr = [12, 11, 13, 5, 6, 7]
print(heap_sort(arr))[5, 6, 7, 11, 12, 13]
Heap Sort сортирует на месте, имеет гарантированную сложность O(n log n). Построение кучи занимает O(n), а извлечение элементов – O(n log n). Алгоритм нестабилен.
Алгоритм Кнута-Морриса-Пратта (KMP) для поиска подстроки
def kmp_search(text, pattern):
def compute_lps(pattern):
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lps
lps = compute_lps(pattern)
i = j = 0
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
return i - j # Найдено
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return -1
text = 'abcababcabc'
pattern = 'abcabc'
print(kmp_search(text, pattern))3
KMP избегает повторного сравнения символов, используя префикс-функцию. Время работы – O(n + m), где n – длина текста, m – длина образца. Подходит для ситуаций, когда требуется многократный поиск в одном тексте.
Алгоритм Дейкстры для поиска кратчайшего пути во взвешенном графе
import heapq
def dijkstra(graph, start):
distances = {node: float('inf') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
visited = set()
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_node in visited:
continue
visited.add(current_node)
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A')){'A': 0, 'B': 1, 'C': 3, 'D': 4}Алгоритм Дейкстры находит кратчайшие пути от начальной вершины до всех остальных в графе с неотрицательными весами. Используется в навигационных системах, маршрутизации. Реализация с помощью кучи (heapq) даёт сложность O((V+E) log V).