После рекурсии и динамического программирования (Часть 3), возвращаемся к фундаментальным алгоритмам поиска и сортировки. Выбор правильного алгоритма здесь критичен: он может кардинально повлиять на производительность вашего приложения, особенно на больших данных. Понимание их работы и компромиссов — ключ к эффективности.
def linear_search(data_collection, target):
"""
Ищет target в data_collection линейным поиском.
Возвращает индекс первого найденного элемента или -1.
"""
for index, element in enumerate(data_collection):
if element == target:
print(f"Элемент '{target}' найден на позиции {index}.")
return index
print(f"Элемент '{target}' не найден в коллекции.")
return -1
shopping_list = ["молоко", "хлеб", "яйца", "масло", "сыр", "хлеб"]
target_item1 = "яйца"
target_item2 = "кофе"
target_item3 = "хлеб" # Присутствует дважды
print(f"Ищем '{target_item1}' в списке: {shopping_list}")
linear_search(shopping_list, target_item1) # Элемент 'яйца' найден на позиции 2.
print(f"\nИщем '{target_item2}' в списке: {shopping_list}")
linear_search(shopping_list, target_item2) # Элемент 'кофе' не найден в коллекции.
print(f"\nИщем '{target_item3}' в списке: {shopping_list}")
linear_search(shopping_list, target_item3) # Элемент 'хлеб' найден на позиции 1 Коллекция, в которой выполняется бинарный поиск, ДОЛЖНА БЫТЬ ОТСОРТИРОВАНА!
Если данные расположены хаотично, мы не можем делать вывод о том, в какой половине искать дальше, просто сравнив элемент в середине с искомым.
def binary_search_iterative(sorted_data_collection, target):
"""
Ищет target в ОТСОРТИРОВАННОЙ коллекции итеративным бинарным поиском.
Возвращает индекс или -1.
"""
left, right = 0, len(sorted_data_collection) - 1
while left <= right:
mid = left + (right - left) // 2
current_element = sorted_data_collection[mid]
if current_element == target:
print(f"Элемент '{target}' найден на позиции {mid}.")
return mid
elif target < current_element:
right = mid - 1
else:
left = mid + 1
print(f"Элемент '{target}' не найден в коллекции.")
return -1
sorted_employees = ["Андреев", "Борисов", "Волков", "Григорьев", "Дмитриев", "Егоров", "Зайцев", "Иванов", "Кузнецов", "Лебедев"]
sorted_prices = [150, 299, 450, 800, 1150, 1999, 2500, 3800, 5000]
binary_search_iterative(sorted_employees, "Иванов") # Элемент 'Иванов' найден на позиции 7.
binary_search_iterative(sorted_employees, "Петров") # Элемент 'Петров' не найден в коллекции.
binary_search_iterative(sorted_prices, 1999) # Элемент '1999' найден на позиции 5.
binary_search_iterative(sorted_prices, 1000) # Элемент '1000' не найден в коллекции.import bisect
sorted_employees = ["Андреев", "Борисов", "Волков", "Григорьев", "Дмитриев", "Егоров", "Зайцев", "Иванов", "Кузнецов", "Лебедев"]
sorted_duplicates = [10, 20, 20, 20, 30, 40]
def find_with_bisect(sorted_list, target):
"""Ищет target в отсортированном списке с помощью bisect_left."""
print(f"Ищем '{target}' с помощью bisect в {sorted_list}")
index = bisect.bisect_left(sorted_list, target) # O(log n)
if index < len(sorted_list) and sorted_list[index] == target:
print(f"Элемент '{target}' найден на позиции {index}.")
return index
else:
print(f"Элемент '{target}' не найден.")
return -1
find_with_bisect(sorted_employees, "Иванов") # Элемент 'Иванов' найден на позиции 7.
find_with_bisect(sorted_employees, "Петров") # Элемент 'Петров' не найден.
find_with_bisect(sorted_duplicates, 20) # Элемент '20' найден на позиции 1.Выбор между линейным и бинарным поиском — это классический пример компромисса между подготовкой данных и скоростью выполнения операции.
Линейный поиск (O(n))
Бинарный поиск (O(log n))
def selection_sort(data_list):
"""Сортирует data_list при помощи selection sort."""
n = len(data_list)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if data_list[j] < data_list[min_index]:
min_index = j
# Оптимизация: меняем только если нашли меньший элемент
if min_index != i:
data_list[i], data_list[min_index] = data_list[min_index], data_list[i]
# print(f" После шага {i+1}: {data_list}") # Отладка шагов
print(f"Отсортированный список: {data_list}")
return data_list
items_to_select = [64, 25, 12, 22, 11, 90]
selection_sort(items_to_select) # [11, 12, 22, 25, 64, 90]def bubble_sort(data_list):
"""Сортирует data_list на месте пузырьковым методом (с оптимизацией)."""
n = len(data_list)
print(f"Начальный список: {data_list}")
for i in range(n):
swapped = False # Флаг для оптимизации
# Внутренний цикл: проходим до n-i-1
for j in range(0, n - i - 1):
if data_list[j] > data_list[j + 1]:
data_list[j], data_list[j + 1] = data_list[j + 1], data_list[j]
swapped = True
# print(f" После прохода {i+1}: {data_list}") # Отладка
# Если обменов не было, прерываем
if not swapped:
break
print(f"Отсортированный список: {data_list}")
return data_list
items_to_bubble = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(items_to_bubble.copy()) # [11, 12, 22, 25, 34, 64, 90]def insertion_sort(data_list):
"""Сортирует data_list на месте методом вставки."""
n = len(data_list)
print(f"Начальный список: {data_list}")
for i in range(1, n):
key = data_list[i] # Элемент для вставки
j = i - 1 # Последний индекс в отсортированной части
# Сдвигаем элементы > key вправо
while j >= 0 and key < data_list[j]:
data_list[j + 1] = data_list[j]
j -= 1
# Вставляем key на правильное место
data_list[j + 1] = key
# print(f" После шага {i} (вставили {key}): {data_list}")
print(f"Отсортированный список: {data_list}")
return data_list
items_to_insert = [12, 11, 13, 5, 6]
insertion_sort(items_to_insert.copy()) # [5, 6, 11, 12, 13]def merge_sort(data_list):
"""Сортирует data_list методом слияния (рекурсивно). Возвращает НОВЫЙ список."""
n = len(data_list)
if n <= 1: # Базовый случай
return data_list
# 1. Разделяй
mid = n // 2
left_half = data_list[:mid]
right_half = data_list[mid:]
# 2. Властвуй (рекурсивно)
sorted_left = merge_sort(left_half)
sorted_right = merge_sort(right_half)
# 3. Соединяй (слияние)
merged_list = []
i = j = 0
while i < len(sorted_left) and j < len(sorted_right):
# Используем <= для стабильности
if sorted_left[i] <= sorted_right[j]:
merged_list.append(sorted_left[i])
i += 1
else:
merged_list.append(sorted_right[j])
j += 1
# Добавляем остатки
merged_list.extend(sorted_left[i:])
merged_list.extend(sorted_right[j:])
return merged_list
items_to_merge = [12, 11, 13, 5, 6, 7, 5]
sorted_merged = merge_sort(items_to_merge.copy()) # merge_sort возвращает новый список
print(f"Отсортированный список: {sorted_merged}") # [5, 5, 6, 7, 11, 12, 13]def partition(data_list, low, high):
"""Разбиение для Quick Sort (опора - последний элемент)."""
pivot = data_list[high]
i = low - 1 # Индекс для меньших элементов
for j in range(low, high):
if data_list[j] <= pivot:
i += 1
data_list[i], data_list[j] = data_list[j], data_list[i]
# Ставим опору на место
final_pivot_index = i + 1
data_list[final_pivot_index], data_list[high] = data_list[high], data_list[final_pivot_index]
return final_pivot_index
def quick_sort_recursive(data_list, low, high):
"""Рекурсивная часть Quick Sort."""
if low < high:
pi = partition(data_list, low, high) # Индекс опоры
quick_sort_recursive(data_list, low, pi - 1) # Сортируем левую часть
quick_sort_recursive(data_list, pi + 1, high)# Сортируем правую часть
def quick_sort(data_list):
"""Запускает Quick Sort для всего списка (сортирует на месте)."""
n = len(data_list)
quick_sort_recursive(data_list, 0, n - 1)
return data_list
items_to_quick = [10, 7, 8, 9, 1, 5]
sorted_list = items_to_quick.copy()
quick_sort(sorted_list)
print(f"Отсортированный список: {sorted_list}") # [1, 5, 7, 8, 9, 10]numbers = [12, -5, 11, 0, 13, 5, 6, -2]
words = ["banana", "Apple", "Киви", "date", "Банан"]
users = [
{'name': 'Олег', 'age': 33, 'id': 3},
{'name': 'Катя', 'age': 32, 'id': 2},
{'name': 'Кира', 'age': 1, 'id': 1}
]
# 1. Сортировка списка на месте
numbers_copy = numbers.copy()
numbers_copy.sort(reverse=True) # По убыванию
print(f"\nnumbers.sort(reverse=True): {numbers_copy}") # [13, 12, 11, 6, 5, 0, -2, -5]
# 2. Новый отсортированный список слов без учета регистра
sorted_words_ci = sorted(words, key=str.lower)
print(f"sorted(words, key=str.lower): {sorted_words_ci}") # ['Apple', 'banana', 'date', 'Банан', 'Киви']
# 3. Сортировка пользователей по возрасту, затем по ID (стабильность Timsort!)
# Используем кортеж в lambda для многоуровневой сортировки
sorted_users = sorted(users, key=lambda user: (user['age'], user['id']))
print(f"Пользователи по возрасту, затем ID: {sorted_users}")
# [{'name': 'Кира', 'age': 1, 'id': 1}, {'name': 'Катя', 'age': 32, 'id': 2}, {'name': 'Олег', 'age': 33, 'id': 3}]Вывод
Производительность имеет значение! Выбор между O(n) и O(log n) для поиска или между O(n²) и O(n log n) для сортировки может кардинально повлиять на скорость работы вашего приложения при росте данных. К счастью, Python предоставляет высокооптимизированные встроенные инструменты, которые в большинстве случаев являются лучшим выбором. Понимание того, как они работают, позволяет применять их максимально эффективно.