Объяснение алгоритмов сортировки с примерами на Python

В этой статье будут рассмотрены популярные алгоритмы, принципы их работы и реализация на Python. А ещё сравним, как быстро они сортируют элементы в списке.

В качестве общего примера возьмём сортировку чисел в порядке возрастания. Но эти методы можно легко адаптировать под ваши потребности.

Пузырьковая сортировка

Этот простой алгоритм выполняет итерации по списку, сравнивая элементы попарно и меняя их местами, пока более крупные элементы не «всплывут» в начало списка, а более мелкие не останутся на «дне».

Алгоритм

Сначала сравниваются первые два элемента списка. Если первый элемент больше, они меняются местами. Если они уже в нужном порядке, оставляем их как есть. Затем переходим к следующей паре элементов, сравниваем их значения и меняем местами при необходимости. Этот процесс продолжается до последней пары элементов в списке.

При достижении конца списка процесс повторяется заново для каждого элемента. Это крайне неэффективно, если в массиве нужно сделать, например, только один обмен. Алгоритм повторяется n? раз, даже если список уже отсортирован.

Для оптимизации алгоритма нужно знать, когда его остановить, то есть когда список отсортирован.

Чтобы остановить алгоритм по окончании сортировки, нужно ввести переменную-флаг. Когда значения меняются местами, устанавливаем флаг в значение True, чтобы повторить процесс сортировки. Если перестановок не произошло, флаг остаётся False и алгоритм останавливается.

Реализация

def bubble_sort(nums):       # Устанавливаем swapped в True, чтобы цикл запустился хотя бы один раз     swapped = True     while swapped:         swapped = False         for i in range(len(nums) - 1):             if nums[i] > nums[i + 1]:                 # Меняем элементы                 nums[i], nums[i + 1] = nums[i + 1], nums[i]                 # Устанавливаем swapped в True для следующей итерации                 swapped = True  # Проверяем, что оно работает random_list_of_nums = [5, 2, 1, 8, 4]   bubble_sort(random_list_of_nums)   print(random_list_of_nums)

Алгоритм работает в цикле while и прерывается, когда элементы ни разу не меняются местами. Вначале присваиваем swapped значение True, чтобы алгоритм запустился хотя бы один раз.

Время сортировки

Если взять самый худший случай (изначально список отсортирован по убыванию), затраты времени будут равны O(n?), где n — количество элементов списка.

Оценка сложности алгоритмов, или Что такое О(log n)

tproger.ru

Сортировка выборкой

Этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Наименьший элемент удаляется из второго списка и добавляется в первый.

Алгоритм

На практике не нужно создавать новый список для отсортированных элементов. В качестве него используется крайняя левая часть списка. Находится наименьший элемент и меняется с первым местами.

Теперь, когда нам известно, что первый элемент списка отсортирован, находим наименьший элемент из оставшихся и меняем местами со вторым. Повторяем это до тех пор, пока не останется последний элемент в списке.

Реализация

def selection_sort(nums):       # Значение i соответствует кол-ву отсортированных значений     for i in range(len(nums)):         # Исходно считаем наименьшим первый элемент         lowest_value_index = i         # Этот цикл перебирает несортированные элементы         for j in range(i + 1, len(nums)):             if nums[j] < nums[lowest_value_index]:                 lowest_value_index = j         # Самый маленький элемент меняем с первым в списке         nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i]  # Проверяем, что оно работает random_list_of_nums = [12, 8, 3, 20, 11]   selection_sort(random_list_of_nums)   print(random_list_of_nums) 

По мере увеличения значения i нужно проверять меньше элементов.

Время сортировки

Затраты времени на сортировку выборкой в среднем составляют O(n?), где n — количество элементов списка.

Сортировка вставками

Как и сортировка выборкой, этот алгоритм сегментирует список на две части: отсортированную и неотсортированную. Алгоритм перебирает второй сегмент и вставляет текущий элемент в правильную позицию первого сегмента.

Алгоритм

Предполагается, что первый элемент списка отсортирован. Переходим к следующему элементу, обозначим его х. Если х больше первого, оставляем его на своём месте. Если он меньше, копируем его на вторую позицию, а х устанавливаем как первый элемент.

Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше x или не дойдём до конца списка. В первом случае x помещается на правильную позицию.

Реализация

def insertion_sort(nums):       # Сортировку начинаем со второго элемента, т.к. считается, что первый элемент уже отсортирован     for i in range(1, len(nums)):         item_to_insert = nums[i]         # Сохраняем ссылку на индекс предыдущего элемента         j = i - 1         # Элементы отсортированного сегмента перемещаем вперёд, если они больше         # элемента для вставки         while j >= 0 and nums[j] > item_to_insert:             nums[j + 1] = nums[j]             j -= 1         # Вставляем элемент         nums[j + 1] = item_to_insert  # Проверяем, что оно работает random_list_of_nums = [9, 1, 15, 28, 6]   insertion_sort(random_list_of_nums)   print(random_list_of_nums)

Время сортировки

Время сортировки вставками в среднем равно O(n?), где n — количество элементов списка.

Пирамидальная сортировка

Также известна как сортировка кучей. Этот популярный алгоритм, как и сортировки вставками или выборкой, сегментирует список на две части: отсортированную и неотсортированную. Алгоритм преобразует второй сегмент списка в структуру данных «куча» (heap), чтобы можно было эффективно определить самый большой элемент.

Алгоритм

Сначала преобразуем список в Max Heap — бинарное дерево, где самый большой элемент является вершиной дерева. Затем помещаем этот элемент в конец списка. После перестраиваем Max Heap и снова помещаем новый наибольший элемент уже перед последним элементом в списке.

Этот процесс построения кучи повторяется, пока все вершины дерева не будут удалены.

Реализация

Создадим вспомогательную функцию heapify() для реализации этого алгоритма:

def heapify(nums, heap_size, root_index):       # Индекс наибольшего элемента считаем корневым индексом     largest = root_index     left_child = (2 * root_index) + 1     right_child = (2 * root_index) + 2      # Если левый потомок корня — допустимый индекс, а элемент больше,     # чем текущий наибольший, обновляем наибольший элемент     if left_child < heap_size and nums[left_child] > nums[largest]:         largest = left_child      # То же самое для правого потомка корня     if right_child < heap_size and nums[right_child] > nums[largest]:         largest = right_child      # Если наибольший элемент больше не корневой, они меняются местами     if largest != root_index:         nums[root_index], nums[largest] = nums[largest], nums[root_index]         # Heapify the new root element to ensure it's the largest         heapify(nums, heap_size, largest)  def heap_sort(nums):       n = len(nums)      # Создаём Max Heap из списка     # Второй аргумент означает остановку алгоритма перед элементом -1, т.е.     # перед первым элементом списка     # 3-й аргумент означает повторный проход по списку в обратном направлении,      # уменьшая счётчик i на 1      for i in range(n, -1, -1):         heapify(nums, n, i)      # Перемещаем корень Max Heap в конец списка     for i in range(n - 1, 0, -1):         nums[i], nums[0] = nums[0], nums[i]         heapify(nums, i, 0)  # Проверяем, что оно работает random_list_of_nums = [35, 12, 43, 8, 51]   heap_sort(random_list_of_nums)   print(random_list_of_nums)

Время сортировки

В среднем время сортировки кучей составляет O(n log n), что уже значительно быстрее предыдущих алгоритмов.

Сортировка слиянием

Этот алгоритм относится к алгоритмам «разделяй и властвуй». Он разбивает список на две части, каждую из них он разбивает ещё на две и т. д. Список разбивается пополам, пока не останутся единичные элементы.

Соседние элементы становятся отсортированными парами. Затем эти пары объединяются и сортируются с другими парами. Этот процесс продолжается до тех пор, пока не отсортируются все элементы.

Алгоритм

Список рекурсивно разделяется пополам, пока в итоге не получатся списки размером в один элемент. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Это происходит до тех пор, пока не получится полный отсортированный список.

Сортировка осуществляется путём сравнения наименьших элементов каждого подмассива. Первые элементы каждого подмассива сравниваются первыми. Наименьший элемент перемещается в результирующий массив. Счётчики результирующего массива и подмассива, откуда был взят элемент, увеличиваются на 1.

Реализация

def merge(left_list, right_list):       sorted_list = []     left_list_index = right_list_index = 0      # Длина списков часто используется, поэтому создадим переменные для удобства     left_list_length, right_list_length = len(left_list), len(right_list)      for _ in range(left_list_length + right_list_length):         if left_list_index < left_list_length and right_list_index < right_list_length:             # Сравниваем первые элементы в начале каждого списка             # Если первый элемент левого подсписка меньше, добавляем его             # в отсортированный массив             if left_list[left_list_index] <= right_list[right_list_index]:                 sorted_list.append(left_list[left_list_index])                 left_list_index += 1             # Если первый элемент правого подсписка меньше, добавляем его             # в отсортированный массив             else:                 sorted_list.append(right_list[right_list_index])                 right_list_index += 1          # Если достигнут конец левого списка, элементы правого списка         # добавляем в конец результирующего списка         elif left_list_index == left_list_length:             sorted_list.append(right_list[right_list_index])             right_list_index += 1         # Если достигнут конец правого списка, элементы левого списка         # добавляем в отсортированный массив         elif right_list_index == right_list_length:             sorted_list.append(left_list[left_list_index])             left_list_index += 1      return sorted_list  def merge_sort(nums):       # Возвращаем список, если он состоит из одного элемента     if len(nums) <= 1:         return nums      # Для того чтобы найти середину списка, используем деление без остатка     # Индексы должны быть integer     mid = len(nums) // 2      # Сортируем и объединяем подсписки     left_list = merge_sort(nums[:mid])     right_list = merge_sort(nums[mid:])      # Объединяем отсортированные списки в результирующий     return merge(left_list, right_list)  # Проверяем, что оно работает random_list_of_nums = [120, 45, 68, 250, 176]   random_list_of_nums = merge_sort(random_list_of_nums)   print(random_list_of_nums)

Обратите внимание, что функция merge_sort(), в отличие от предыдущих алгоритмов, возвращает новый список, а не сортирует существующий. Поэтому такая сортировка требует больше памяти для создания нового списка того же размера, что и входной список.

Время сортировки

В среднем время сортировки слиянием составляет O(n log n).

Быстрая сортировка

Этот алгоритм также относится к алгоритмам «разделяй и властвуй». Его используют чаще других алгоритмов, описанных в этой статье. При правильной конфигурации он чрезвычайно эффективен и не требует дополнительной памяти, в отличие от сортировки слиянием. Массив разделяется на две части по разные стороны от опорного элемента. В процессе сортировки элементы меньше опорного помещаются перед ним, а равные или большие —позади.

Алгоритм

Быстрая сортировка начинается с разбиения списка и выбора одного из элементов в качестве опорного. А всё остальное передвигаем так, чтобы этот элемент встал на своё место. Все элементы меньше него перемещаются влево, а равные и большие элементы перемещаются вправо.

Реализация

Существует много вариаций данного метода. Способ разбиения массива, рассмотренный здесь, соответствует схеме Хоара (создателя данного алгоритма).

def partition(nums, low, high):       # Выбираем средний элемент в качестве опорного     # Также возможен выбор первого, последнего     # или произвольного элементов в качестве опорного     pivot = nums[(low + high) // 2]     i = low - 1     j = high + 1     while True:         i += 1         while nums[i] < pivot:             i += 1          j -= 1         while nums[j] > pivot:             j -= 1          if i >= j:             return j          # Если элемент с индексом i (слева от опорного) больше, чем         # элемент с индексом j (справа от опорного), меняем их местами         nums[i], nums[j] = nums[j], nums[i]  def quick_sort(nums):       # Создадим вспомогательную функцию, которая вызывается рекурсивно     def _quick_sort(items, low, high):         if low < high:             # This is the index after the pivot, where our lists are split             split_index = partition(items, low, high)             _quick_sort(items, low, split_index)             _quick_sort(items, split_index + 1, high)      _quick_sort(nums, 0, len(nums) - 1)  # Проверяем, что оно работает random_list_of_nums = [22, 5, 1, 18, 99]   quick_sort(random_list_of_nums)   print(random_list_of_nums) 

Время выполнения

В среднем время выполнения быстрой сортировки составляет O(n log n).

Обратите внимание, что алгоритм быстрой сортировки будет работать медленно, если опорный элемент равен наименьшему или наибольшему элементам списка. При таких условиях, в отличие от сортировок кучей и слиянием, обе из которых имеют в худшем случае время сортировки O(n log n), быстрая сортировка в худшем случае будет выполняться O(n?).

Встроенные функции сортировки на Python

Иногда полезно знать перечисленные выше алгоритмы, но в большинстве случаев разработчик, скорее всего, будет использовать функции сортировки, уже предоставленные в языке программирования.

Отсортировать содержимое списка можно с помощью стандартного метода sort():

>>> apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2] >>> apples_eaten_a_day.sort() >>> apples_eaten_a_day [1, 1, 1, 2, 2, 2, 3]

Или можно использовать функцию sorted() для создания нового отсортированного списка, оставив входной список нетронутым:

>>> apples_eaten_a_day_2 = [2, 1, 1, 3, 1, 2, 2] >>> sorted_apples = sorted(apples_eaten_a_day_2) >>> sorted_apples [1, 1, 1, 2, 2, 2, 3]

Оба эти метода сортируют в порядке возрастания, но можно изменить порядок, установив для флага reverse значение True:

# Обратная сортировка списка на месте >>> apples_eaten_a_day.sort(reverse=True) >>> apples_eaten_a_day [3, 2, 2, 2, 1, 1, 1]  # Обратная сортировка, чтобы получить новый список >>> sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True) >>> sorted_apples_desc [3, 2, 2, 2, 1, 1, 1]

В отличие от других алгоритмов, обе функции в Python могут сортировать также списки кортежей и классов. Функция sorted() может сортировать любую последовательность, которая включает списки, строки, кортежи, словари, наборы и пользовательские итераторы, которые вы можете создать.

Функции в Python реализуют алгоритм Tim Sort, основанный на сортировке слиянием и сортировке вставкой.

Сравнение скоростей сортировок

Для сравнения сгенерируем массив из 5000 чисел от 0 до 1000. Затем определим время, необходимое для завершения каждого алгоритма. Повторим каждый метод 10 раз, чтобы можно было более точно установить, насколько каждый из них производителен.

Пузырьковая сортировка — самый медленный из всех алгоритмов. Возможно, он будет полезен как введение в тему алгоритмов сортировки, но не подходит для практического использования.
Быстрая сортировка хорошо оправдывает своё название, почти в два раза быстрее, чем сортировка слиянием, и не требуется дополнительное место для результирующего массива.
Сортировка вставками выполняет меньше сравнений, чем сортировка выборкой и в реальности должна быть производительнее, но в данном эксперименте она выполняется немного медленней. Сортировка вставками делает гораздо больше обменов элементами. Если эти обмены занимают намного больше времени, чем сравнение самих элементов, то такой результат вполне закономерен.

Вы познакомились с шестью различными алгоритмами сортировок и их реализациями на Python. Масштаб сравнения и количество перестановок, которые выполняет алгоритм вместе со средой выполнения кода, будут определяющими факторами в производительности. В реальных приложениях Python рекомендуется использовать встроенные функции сортировки, поскольку они реализованы именно для удобства разработчика.

Лучше понять эти алгоритмы вам поможет их визуализация.

Перевод статьи «Sorting Algorithms in Python»

Источник: m.vk.com

Комментарии: