Вступление

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

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

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

Если вы хотите узнать о конкретном алгоритме, вы можете перейти к нему здесь:

• Пузырьковая сортировка
• Выбор Сортировка
• Сортировка вставкой
• Сортировка слиянием
• Сортировка кучи
• Быстрая сортировка
• Сортировка в Python

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

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

Объяснение

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

Достигнув конца списка, он повторяет этот процесс для каждого элемента. Хотя это крайне неэффективно. Что, если в массиве нужно сделать только один своп? Зачем нам повторять итерацию n ^ 2 раз, даже если она уже отсортирована?

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

Как мы узнаем, что сортировка закончена? Если бы предметы были в порядке, нам бы не пришлось их менять. Итак, всякий раз, когда мы меняем местами значения, мы устанавливаем флаг в True чтобы повторить процесс сортировки. Если свопы не произошли, флаг останется False и алгоритм остановится.

Выполнение

С помощью оптимизации мы можем реализовать пузырьковую сортировку в Python следующим образом:

 def bubble_sort(nums): 
 # We set swapped to True so the loop looks runs at least once 
 swapped = True 
 while swapped: 
 swapped = False 
 for i in range(len(nums) - 1): 
 if nums[i] > nums[i + 1]: 
 # Swap the elements 
 nums[i], nums[i + 1] = nums[i + 1], nums[i] 
 # Set the flag to True so we'll loop again 
 swapped = True 
 
 
 # Verify it works 
 random_list_of_nums = [5, 2, 1, 8, 4] 
 bubble_sort(random_list_of_nums) 
 print(random_list_of_nums) 

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

Сложность времени

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

Следовательно, если у нас есть n элементов в нашем списке, у нас будет n итераций для каждого элемента - таким образом, временная сложность пузырьковой сортировки составляет O (n ^ 2) .

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

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

Объяснение

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

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

Выполнение

 def selection_sort(nums): 
 # This value of i corresponds to how many values were sorted 
 for i in range(len(nums)): 
 # We assume that the first item of the unsorted segment is the smallest 
 lowest_value_index = i 
 # This loop iterates over the unsorted items 
 for j in range(i + 1, len(nums)): 
 if nums[j] < nums[lowest_value_index]: 
 lowest_value_index = j 
 # Swap values of the lowest unsorted element with the first unsorted 
 # element 
 nums[i], nums[lowest_value_index] = nums[lowest_value_index], nums[i] 
 
 
 # Verify it works 
 random_list_of_nums = [12, 8, 3, 20, 11] 
 selection_sort(random_list_of_nums) 
 print(random_list_of_nums) 

Мы видим, что с i нам нужно проверять меньше элементов.

Сложность времени

Мы можем легко получить временную сложность, исследуя for в алгоритме сортировки выбора. Для списка из n элементов внешний цикл повторяется n раз.

Внутренний цикл выполняет итерацию n-1, когда i равно 1, а затем n-2, когда i равно 2, и так далее.

Количество сравнений составляет (n - 1) + (n - 2) + ... + 1 , что дает сортировке выбора временная сложность O (n ^ 2) .

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

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

Объяснение

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

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

Если вы хотите прочитать подробную статью о сортировке вставкой , мы вам поможем!

Выполнение

 def insertion_sort(nums): 
 # Start on the second element as we assume the first element is sorted 
 for i in range(1, len(nums)): 
 item_to_insert = nums[i] 
 # And keep a reference of the index of the previous element 
 j = i - 1 
 # Move all items of the sorted segment forward if they are larger than 
 # the item to insert 
 while j >= 0 and nums[j] > item_to_insert: 
 nums[j + 1] = nums[j] 
 j -= 1 
 # Insert the item 
 nums[j + 1] = item_to_insert 
 
 
 # Verify it works 
 random_list_of_nums = [9, 1, 15, 28, 6] 
 insertion_sort(random_list_of_nums) 
 print(random_list_of_nums) 

Сложность времени

В худшем случае массив будет отсортирован в обратном порядке. Внешний for loop в функции сортировки вставкой всегда повторяется n-1 раз.

В худшем случае внутренний for loop местами один раз, затем два и так далее. Тогда количество свопов будет 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1) что дает сортировке вставкой временную сложность O (n ^ 2) .

Сортировка кучи

Этот популярный алгоритм сортировки, как и сортировка Вставка и Выбор, сегментирует список на отсортированные и несортированные части. Он преобразует несортированный сегмент списка в структуру данных кучи, чтобы мы могли эффективно определить самый большой элемент.

Объяснение

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

Мы повторяем этот процесс построения кучи, пока не будут удалены все узлы.

Если вы хотите прочитать подробную статью о Heap Sort , мы вам поможем!

Выполнение

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

 def heapify(nums, heap_size, root_index): 
 # Assume the index of the largest element is the root index 
 largest = root_index 
 left_child = (2 * root_index) + 1 
 right_child = (2 * root_index) + 2 
 
 # If the left child of the root is a valid index, and the element is greater 
 # than the current largest element, then update the largest element 
 if left_child < heap_size and nums[left_child] > nums[largest]: 
 largest = left_child 
 
 # Do the same for the right child of the root 
 if right_child < heap_size and nums[right_child] > nums[largest]: 
 largest = right_child 
 
 # If the largest element is no longer the root element, swap them 
 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) 
 
 # Create a Max Heap from the list 
 # The 2nd argument of range means we stop at the element before -1 ie 
 # the first element of the list. 
 # The 3rd argument of range means we iterate backwards, reducing the count 
 # of i by 1 
 for i in range(n, -1, -1): 
 heapify(nums, n, i) 
 
 # Move the root of the max heap to the end of 
 for i in range(n - 1, 0, -1): 
 nums[i], nums[0] = nums[0], nums[i] 
 heapify(nums, i, 0) 
 
 
 # Verify it works 
 random_list_of_nums = [35, 12, 43, 8, 51] 
 heap_sort(random_list_of_nums) 
 print(random_list_of_nums) 

Сложность времени

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

Визуализируйте двоичное дерево с 3 элементами, оно имеет высоту 2. Теперь визуализируйте двоичное дерево с 7 элементами, оно имеет высоту 3. Дерево логарифмически растет до n . Функция heapify обходит это дерево за время O (log (n)) .

Функция heap_sort выполняет итерацию по массиву n раз. Следовательно, общая временная сложность алгоритма сортировки кучи составляет O (nlog (n)) .

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

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

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

Объяснение

Мы рекурсивно разделяем список пополам, пока не получим списки с размером один. Затем мы объединяем каждую половину, которая была разделена, сортируя их в процессе.

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

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

Если вы хотите прочитать подробную статью о сортировке слиянием , мы вам поможем!

Выполнение

 def merge(left_list, right_list): 
 sorted_list = [] 
 left_list_index = right_list_index = 0 
 
 # We use the list lengths often, so its handy to make variables 
 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: 
 # We check which value from the start of each list is smaller 
 # If the item at the beginning of the left list is smaller, add it 
 # to the sorted list 
 if left_list[left_list_index] <= right_list[right_list_index]: 
 sorted_list.append(left_list[left_list_index]) 
 left_list_index += 1 
 # If the item at the beginning of the right list is smaller, add it 
 # to the sorted list 
 else: 
 sorted_list.append(right_list[right_list_index]) 
 right_list_index += 1 
 
 # If we've reached the end of the of the left list, add the elements 
 # from the right list 
 elif left_list_index == left_list_length: 
 sorted_list.append(right_list[right_list_index]) 
 right_list_index += 1 
 # If we've reached the end of the of the right list, add the elements 
 # from the left list 
 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 the list is a single element, return it 
 if len(nums) <= 1: 
 return nums 
 
 # Use floor division to get midpoint, indices must be integers 
 mid = len(nums) // 2 
 
 # Sort and merge each half 
 left_list = merge_sort(nums[:mid]) 
 right_list = merge_sort(nums[mid:]) 
 
 # Merge the sorted lists into a new one 
 return merge(left_list, right_list) 
 
 
 # Verify it works 
 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() , в отличие от предыдущих алгоритмов сортировки, возвращает новый отсортированный список, а не сортирует существующий список.

Следовательно, сортировке слиянием требуется место для создания нового списка того же размера, что и входной список.

Сложность времени

Давайте сначала посмотрим на функцию merge Он берет два списка и повторяет n раз, где n - размер их объединенного ввода.

Функция merge_sort разбивает заданный массив на 2 и рекурсивно сортирует подмассивы. Поскольку рекурсивный ввод составляет половину того, что было дано, как и в случае с бинарными деревьями, время, необходимое для обработки, логарифмически увеличивается до n .

Следовательно, общая временная сложность алгоритма сортировки слиянием составляет O (nlog (n)) .

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

Этот алгоритм «разделяй и властвуй» - наиболее часто используемый алгоритм сортировки, описанный в этой статье. При правильной настройке он чрезвычайно эффективен и не требует дополнительного пространства, которое использует сортировка слиянием. Мы разбиваем список вокруг опорного элемента, сортируя значения вокруг опорного элемента.

Объяснение

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

Зная, что точка поворота находится на своем законном месте, мы рекурсивно сортируем значения вокруг точки поворота, пока не будет отсортирован весь список.

Если вы хотите прочитать подробную статью о Quick Sort , у нас есть все необходимое!

Выполнение

 # There are different ways to do a Quick Sort partition, this implements the 
 # Hoare partition scheme. Tony Hoare also created the Quick Sort algorithm. 
 def partition(nums, low, high): 
 # We select the middle element to be the pivot. Some implementations select 
 # the first element or the last element. Sometimes the median value becomes 
 # the pivot, or a random one. There are many more strategies that can be 
 # chosen or created. 
 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 
 
 # If an element at i (on the left of the pivot) is larger than the 
 # element at j (on right right of the pivot), then swap them 
 nums[i], nums[j] = nums[j], nums[i] 
 
 
 def quick_sort(nums): 
 # Create a helper function that will be called recursively 
 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) 
 
 
 # Verify it works 
 random_list_of_nums = [22, 5, 1, 18, 99] 
 quick_sort(random_list_of_nums) 
 print(random_list_of_nums) 

Сложность времени

Наихудший сценарий - когда в качестве опорного всегда выбирается самый маленький или самый большой элемент. Это создаст разделы размером n-1 , вызывая рекурсивные вызовы n-1 раз. Это приводит нас к наихудшей временной сложности O (n ^ 2) .

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

При правильном повороте функция быстрой сортировки разделит массив на половины, которые логарифмически растут с увеличением n . Следовательно, средняя временная сложность алгоритма быстрой сортировки составляет O (nlog (n)) .

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

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

Мы можем изменить наш список, чтобы его содержимое было отсортировано с помощью метода sort()

 apples_eaten_a_day = [2, 1, 1, 3, 1, 2, 2] 
 apples_eaten_a_day.sort() 
 print(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) 
 print(sorted_apples) # [1, 1, 1, 2, 2, 2, 3] 

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

 # Reverse sort the list in-place 
 apples_eaten_a_day.sort(reverse=True) 
 print(apples_eaten_a_day) # [3, 2, 2, 2, 1, 1, 1] 
 
 # Reverse sort to get a new list 
 sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True) 
 print(sorted_apples_desc) # [3, 2, 2, 2, 1, 1, 1] 

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

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

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

Чтобы получить представление о том, насколько быстро они работают, мы генерируем список из 5000 чисел от 0 до 1000. Затем мы измеряем время, необходимое для выполнения каждого алгоритма. Это повторяется 10 раз, чтобы мы могли более надежно установить образец производительности.

Вот результаты, время в секундах:

Запустить Пузырь Выбор Вставка Куча Объединить Быстро

1 5,53188 1,23152 1,60355 0,04006 0,02619 0,01639 2 4,92176 1,24728 1,59103 0,03999 0,02584 0,01661 3 4,91642 1,22440 1,59362 0,04407 0,02862 0,01646 4 5,15470 1,25053 1,63463 0,04128 0,02882 0,01860 5 4,95522 1,28987 1,61759 0,04515 0,03314 0,01885 6 5,04907 1,25466 1,62515 0,04257 0,02595 0,01628 7 5,05591 1,24911 1,61981 0,04028 0,02733 0,01760 8 5,08799 1,25808 1,62603 0,04264 0,02633 0,01705 9 5,03289 1,24915 1,61446 0,04302 0,03293 0,01762 10 5,14292 1,22021 1,57273 0,03966 0,02572 0,01606 Средн. 5,08488 1,24748 1,60986 0,04187 0,02809 0,01715

Вы получите разные значения, если настроите тест самостоятельно, но наблюдаемые закономерности должны быть одинаковыми или похожими. Пузырьковая сортировка - самый медленный и худший из всех алгоритмов. Хотя он полезен как введение в сортировку и алгоритмы, он не подходит для практического использования.

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

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

Сортировка вставкой заменяет гораздо больше, чем сортировка по выбору. Если замена значений занимает значительно больше времени, чем сравнение значений, то такой «противоположный» результат будет правдоподобным.

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

Заключение

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

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