Алгоритмы сортировки помогают программистам упорядочивать данные, организовывать к ним быстрый доступ — а значит, ускорять разработку и работу будущего сервиса. Рассказываем про несколько алгоритмов, которые можно использовать в Python.
Зачем нужны алгоритмы сортировки
Представьте большую коробку с монетами разных номиналов со всего мира. В ней нужно найти 100 японских иен. В таком хаосе, скорее всего, придется перебирать каждую монетку, похожую на ту, что надо найти. На это уйдет много времени и сил. Самый простой способ ускорить процесс — рассортировать все монеты по маленьким коробочкам, выделив отдельное место для каждой валюты.
Теперь поиск будет значительно быстрее, ведь мы точно знаем, где находятся все иены. Но нет предела совершенству, поэтому можно еще улучшить поиск. Теперь в коробочке с иенами можно разложить все монеты одного номинала в отдельные конверты. В итоге поиск 100 японских иен сводится к двум действиям: найти коробку с иенами, а в ней найти конверт с нужным номиналом.
Благодаря сортировке удалось оптимизировать хранение монет и ускорить поиск нужной. Кроме того, теперь мы можем точно спрогнозировать количество шагов, которое потребуется для поиска любой монеты, и рассчитать примерное время. Перебирая все подряд, не получишь настолько точные результаты еще до начала поиска. Можно вытащить нужную монету с первого раза, а можно перебрать всю коробку и узнать, что ее там нет.
Сортировки в программировании также помогают оптимизировать хранение данных, ускорять поиск информации, прогнозировать выполнение сложных операций и экономить ресурсы. Но при этом есть большой выбор алгоритмов сортировки разной сложности и скорости. У каждого свои плюсы и минусы.
Сортировка пузырьком (Bubble sort)
Самый простой и известный способ сортировки элементов массива. Вместе с этим это самый неэффективный алгоритм, на выполнение которого уходит много времени. Разницу во времени сложно заметить на маленьких массивах, но если данных много, то их сортировка затянется. Особенно плохо «пузырьковая сортировка» работает на массивах с малыми элементами в самом конце.
Суть алгоритма заключается в последовательном сравнении значений соседних элементов массива. Если следующий элемент меньше текущего, то мы их меняем местами. Повторять это действие нужно до тех пор, пока элементы массива не займут свое порядковое место. Если дошли до конца массива, а данные в нем еще не рассортированы, нужно начать проходить сначала.
Реализация алгоритма сортировки пузырьком на Python выглядит так:
def bubble_sort(arr):
n = len(arr)
# Внешний цикл проходит по всем элементам массива
for i in range(n - 1):
# Внутренний цикл проходит от 0 до n-i-1
for j in range(0, n - i - 1):
# Сравниваем соседние элементы
if arr[j] > arr[j + 1]:
# Если текущий элемент больше следующего, меняем их местами
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
unsorted_list = [64, 25, 12, 22, 11]
sorted_list = bubble_sort(unsorted_list)
print("Отсортированный список:", sorted_list)
Теперь попробуем с его помощью отсортировать небольшой массив:
unsorted_list = [64, 25, 12, 22, 11] sorted_list = bubble_sort(unsorted_list) print(sorted_list) >>> [11, 12, 22, 25, 64]
Мы смогли отсортировать массив, но важно помнить, что время выполнения такой сортировки одинаково плохое во всех случаях. Особенно это будет заметно на больших данных.
Сортировка перемешиванием (Cocktail sort)
Сортировку перемешиванием иногда называют двунаправленной или шейкерной. Алгоритм представляет собой улучшенную версию сортировки пузырьком, который решает проблему последних элементов. К примеру, если в конце массива находится самый маленький элемент, то на каждой итерации он будет сдвигаться только на одну позицию.
Для решения этой проблемы сортировка перемешиванием проходится по массиву два раза, меняя направление. В первом случае выполнение алгоритма идет с начала массива, сравнивая попарно соседние элементы. Местами они меняются в том случае, если элемент слева больше элемента справа. Если дошли до конца, то меняем направление и идем к началу. В этом случае меньшие элементы перемещаются влево. Алгоритм выполняется до тех пор, пока все элементы не займут свои места.
Главный плюс сортировки перемешиванием в том, что уменьшается количество итераций сортировки. При этом преимуществе алгоритм все равно остается медленным и показывает плохие результаты на больших наборах данных.
Реализация алгоритма сортировки перемешиванием на Python выглядит так:
def cocktail_sort(arr):
n = len(arr)
# Инициализация переменных для границ массива
start = 0
end = n - 1
while start < end:
# Проход слева направо, аналогично пузырьковой сортировке
for i in range(start, end):
if arr[i] > arr[i + 1]:
# Если текущий элемент больше следующего, меняем их местами
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# Уменьшаем правую границу, так как самый большой элемент уже находится на правильной позиции
end -= 1
# Проход справа налево
for i in range(end - 1, start - 1, -1):
if arr[i] > arr[i + 1]:
# Если текущий элемент больше следующего, меняем их местами
arr[i], arr[i + 1] = arr[i + 1], arr[i]
# Увеличиваем левую границу, так как самый маленький элемент уже находится на правильной позиции
start += 1
return arr
Теперь попробуем с его помощью отсортировать небольшой массив:
unsorted_list = [64, 34, 25, 12, 22, 11, 90] sorted_list = cocktail_sort(unsorted_list) print(sorted_list) >>> [11, 12, 22, 25, 34, 64, 90]
Сортировка вставками (Insertion sort)
Метод сортировки делит массив на две части: отсортированную и общую. В начале выполнения алгоритма считается, что первый элемент массива уже стоит на своем месте. Поэтому массив начинают рассматривать со второго элемента и продолжают так до тех пор, пока все элементы в отсортированной части не окажутся на своих местах.
Пошагово сортировка вставками выглядит так:
- Первый элемент считается отсортированным, а весь массив делится на две части. В первую часть входит первый элемент, а все остальное — неотсортированная часть.
- Берется первый элемент из неотсортированной части.
- Выбранный элемент помещается в правильное место отсортированной части, а остальные элементы в ней сдвигаются.
Последние два шага повторяются по кругу: взяли элемент, нашли ему место и сделали это еще раз. В итоге в отсортированную часть массива должны войти все элементы. Алгоритм сортировки вставками хорошо показывает себя на небольших наборах данных. Кроме того, его можно использовать вместе с другими способами сортировки для оптимизации времени выполнения.
Реализация алгоритма сортировки вставки на Python выглядит так:
def insertion_sort(arr):
# Получаем длину массива
n = len(arr)
# Начинаем со второго элемента, так как считаем, что первый элемент уже отсортирован
for i in range(1, n):
# Текущий элемент, который мы собираемся вставить в отсортированную часть массива
key = arr[i]
# Индекс предыдущего элемента в отсортированной части массива
j = i - 1
# Перемещаем все элементы больше key на одну позицию вперед
# Пока не найдем правильное место для вставки key или не дойдем до начала массива
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# Вставляем key на правильное место в отсортированной части массива
arr[j + 1] = key
return arr
Теперь попробуем отсортировать с его помощью небольшой массив:
unsorted_list = [64, 34, 25, 12, 22, 11, 90] sorted_list = insertion_sort(unsorted_list) print(sorted_list) >>> [11, 12, 22, 25, 34, 64, 90]
Сортировка выбором (Selection sort)
Алгоритм сортировки выбором тоже делит массив на две условные части: отсортированную и общую. Только для вставки берется не первый элемент неотсортированной части, а минимальный. После этого он вставляется в начало отсортированной части.
Пошагово сортировка выбором выглядит следующим образом:
- Из неотсортированной части выбирается элемент с минимальным значением.
- Этот элемент обменивается местами с первым элементом в массиве.
- Поиск в неотсортированной части начинается снова, но уже отсортированные элементы не принимают в этом участие.
Шаги выполняются по кругу до тех пор, пока все элементы массива не будут стоять на своих местах. Если надо отсортировать данные в обратном порядке, то следует искать максимальные элементы вместо минимальных. Важно отметить, что сортировка выбором оказывается неэффективной в больших массивах. Но есть и плюсы: реализация алгоритма занимает мало времени.
Реализация алгоритма сортировки выбором на Python выглядит так:
def selection_sort(arr): n = len(arr) # Проходим по всем элементам массива for i in range(n): # Индекс минимального элемента в неотсортированной части массива min_index = i # Ищем минимальный элемент в неотсортированной части массива for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j # Обмен минимального элемента с первым элементом неотсортированной части arr[i], arr[min_index] = arr[min_index], arr[i] return arr
Теперь попробуем отсортировать с его помощью небольшой массив:
unsorted_list = [64, 34, 25, 12, 22, 11, 90] sorted_list = selection_sort(unsorted_list) print(sorted_list) >>> [11, 12, 22, 25, 34, 64, 90]
Быстрая сортировка (Quicksort)
Это одна из самых быстрых и универсальных сортировок. Алгоритм разработал английский математик Тони Хоар в 1960 году, когда он работал в Московском государственном университете имени М. В. Ломоносова. Алгоритм построен на принципе «Разделяй и властвуй», который подразумевает, что выполнение задачи надо разделить на две такие же подзадачи. Именно алгоритм быстрой сортировки чаще всего применяется в реальных проектах.
В начале выполнения быстрой сортировки необходимо выбрать опорный элемент. Чаще всего это один из крайних элементов, но можно сделать выбор случайным образом. Значение самого элемента не повлияет на скорость работы. После этого массив делится на две части: элементы меньше «опоры» перемещаются влево, а больше — вправо. Далее рекурсивно выполняем деление и сортировку для каждой части до тех пор, пока части не достигнут минимального размера.
Реализация алгоритма быстрой сортировки на Python выглядит так:
def quicksort(arr): if len(arr) <= 1: return arr # Базовый случай: если массив содержит 1 элемент или менее, он уже отсортирован pivot = arr[len(arr) // 2] # Выбор опорного элемента # Разделение массива на три части: элементы меньше, равные и больше опорного left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] # Рекурсивное объединение результатов return quicksort(left) + middle + quicksort(right)
Теперь попробуем отсортировать с его помощью небольшой массив:
unsorted_list = [64, 34, 25, 12, 22, 11, 90] sorted_list = quicksort(unsorted_list) print(sorted_list) >>> [11, 12, 22, 25, 34, 64, 90]
Опытные программисты, какие алгоритмы сортировки выбираете вы? Поделитесь в комментариях, это будет очень полезно для новичков.
