Сортировка выбором в Python: от простого к сложному
Сортировка выбором в Python
Основная идея алгоритма
Сортировка выбором (selection sort) относится к простым алгоритмам сортировки. На каждом шаге находится минимальный (или максимальный) элемент из неотсортированной части массива и меняется местами с первым элементом этой части. Процесс повторяется до полной сортировки. Временная сложность составляет O(n²), дополнительная память O(1) (in-place). Алгоритм не является устойчивым.
Базовая реализация (сортировка по возрастанию)
def selection_sort(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# Пример использования
sample = [64, 25, 12, 22, 11]
selection_sort(sample)
print(sample) # [11, 12, 22, 25, 64]алгоритмы сортировки python (алгоритмы сортировки в python)
Как отсортировать список по убыванию с помощью сортировки выбором?
Для сортировки по убыванию достаточно искать максимальный элемент вместо минимального.
def selection_sort_desc(arr):
n = len(arr)
for i in range(n - 1):
max_idx = i
for j in range(i + 1, n):
if arr[j] > arr[max_idx]:
max_idx = j
if max_idx != i:
arr[i], arr[max_idx] = arr[max_idx], arr[i]
return arr
data = [64, 25, 12, 22, 11]
selection_sort_desc(data)
print(data) # [64, 25, 22, 12, 11]сортировка python примеры (примеры сортировки в python)
Как реализовать сортировку выбором с подсчётом числа перестановок?
Добавляется счётчик обменов, который инкрементируется при каждой замене.
def selection_sort_count(arr):
n = len(arr)
swaps = 0
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
swaps += 1
return arr, swaps
arr = [3, 1, 2]
sorted_arr, swap_count = selection_sort_count(arr)
print(sorted_arr, swap_count) # [1, 2, 3] 2быстрая сортировка python (реализация быстрой сортировки на python)
Как применить сортировку выбором к списку кортежей по заданному ключу?
Алгоритм модифицируется для сравнения по ключу (например, второму элементу кортежа).
def selection_sort_by_key(arr, key_func):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if key_func(arr[j]) < key_func(arr[min_idx]):
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
data = [(1, 'b'), (3, 'a'), (2, 'c')]
selection_sort_by_key(data, lambda x: x[1])
print(data) # [(3, 'a'), (1, 'b'), (2, 'c')]сортировка выбором python (сортировка выбором в python)
Как использовать сортировку выбором с enumerate для упрощения кода?
Метод enumerate позволяет получать индекс и значение одновременно, но для сортировки выбором это не даёт преимуществ, хотя можно записать компактнее.
def selection_sort_enumerate(arr):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j, val in enumerate(arr[i+1:], start=i+1):
if val < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
a = [9, 3, 7, 1]
selection_sort_enumerate(a)
print(a) # [1, 3, 7, 9]сортировка данных python (сортировка данных в python)
Типичные проблемы и ошибки
Проблема 1: Неустойчивость сортировки
Сортировка выбором меняет местами элементы, не сохраняя порядок равных значений. Например, если есть два одинаковых числа, их относительное положение может измениться. Это не ошибка, а свойство алгоритма. Если требуется устойчивая сортировка, выбирают другую (например, пузырьковую или вставками).
Проблема 2: Ошибка при пустом списке
Если на вход подаётся пустой список, цикл for i in range(n - 1) не выполнится, и функция вернёт пустой список без ошибок. Однако если код ожидает какую-то обработку, стоит добавить проверку:
if not arr:
return arrПроблема 3: Попытка сортировки неизменяемого типа (кортеж)
Если аргументом передан кортеж, операция присваивания arr[i], arr[min_idx] = ... вызовет TypeError. Решение – предварительно преобразовать кортеж в список:
def selection_sort(arr):
arr = list(arr) # теперь можно изменять
# ...Проблема 4: Низкая производительность на больших данных
Алгоритм имеет квадратичную сложность. Для списков длиной более нескольких тысяч элементов время выполнения становится заметным. Если важна скорость, стоит рассмотреть более быстрые алгоритмы (быстрая сортировка, Timsort).
Цели и случаи использования
Сортировка выбором подходит для учебных целей, для сортировки небольших объёмов данных (до нескольких сотен элементов) или когда простота реализации важнее производительности. Также она может быть полезна, если нужно минимизировать количество перестановок (не более n-1 обменов).
Расширенные примеры использования сортировки выбором
Пример 1. Сортировка строк по длине (по возрастанию)
def selection_sort_str_by_len(lst):
n = len(lst)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if len(lst[j]) < len(lst[min_idx]):
min_idx = j
if min_idx != i:
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
words = ['python', 'java', 'c', 'javascript']
selection_sort_str_by_len(words)
print(words)['c', 'java', 'python', 'javascript']
Пример 2. Сортировка выбором с пользовательским ключом (аналог sorted key)
def selection_sort_custom(arr, key):
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if key(arr[j]) < key(arr[min_idx]):
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
data = [{'name': 'Alice', 'age': 30}, {'name': 'Bob', 'age': 25}, {'name': 'Eve', 'age': 35}]
selection_sort_custom(data, lambda x: x['age'])
print(data)[{'name': 'Bob', 'age': 25}, {'name': 'Alice', 'age': 30}, {'name': 'Eve', 'age': 35}]
Пример 3. Сортировка выбором по убыванию с дополнительным условием (при равенстве – сортировать по второму полю)
def selection_sort_complex(arr):
n = len(arr)
for i in range(n - 1):
max_idx = i
for j in range(i + 1, n):
# Сначала сравнение по первому полю (убывание)
if (arr[j][0] > arr[max_idx][0]) or \
(arr[j][0] == arr[max_idx][0] and arr[j][1] < arr[max_idx][1]):
max_idx = j
if max_idx != i:
arr[i], arr[max_idx] = arr[max_idx], arr[i]
return arr
pairs = [(5, 'b'), (3, 'a'), (5, 'x'), (3, 'c')]
selection_sort_complex(pairs)
print(pairs)[(5, 'b'), (5, 'x'), (3, 'a'), (3, 'c')]
Пример 4. Визуализация шагов сортировки выбором
def selection_sort_verbose(arr):
n = len(arr)
print("Исходный список:", arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
print(f"Шаг {i+1}: {arr}")
return arr
selection_sort_verbose([7, 2, 9, 1, 5])Исходный список: [7, 2, 9, 1, 5] Шаг 1: [1, 2, 9, 7, 5] Шаг 2: [1, 2, 9, 7, 5] Шаг 3: [1, 2, 5, 7, 9] Шаг 4: [1, 2, 5, 7, 9]
Пример 5. Сортировка выбором для списка чисел с плавающей точкой (обработка NaN)
def selection_sort_floats(arr):
# Удаление NaN или специальная обработка (сравнения с NaN всегда False)
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
# Пропускаем NaN, считая их большими
if arr[j] != arr[j]: # проверка на NaN (idempotent)
continue
if arr[min_idx] != arr[min_idx]: # если min_idx NaN, то заменяем
min_idx = j
elif arr[j] < arr[min_idx]:
min_idx = j
if min_idx != i:
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
import math
data = [3.0, float('nan'), 1.5, 2.2, float('nan')]
sorted_data = selection_sort_floats(data)
print(sorted_data) # NaN останутся на своих местах или в конце, в зависимости от реализации[1.5, 2.2, 3.0, nan, nan]