Рубрики
Без рубрики

Алгоритмы сортировки в Python

Автор оригинала: Marcus Sanatan.

Алгоритмы сортировки в Python

Вступление

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

В этой статье мы рассмотрим популярные алгоритмы сортировки, поймем, как они работают, и закодируем их на 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 , прерываясь только тогда, когда никакие элементы не меняются местами. Мы установили поменяли местами на 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 в функции сортировки вставки всегда повторяется n-1 раз.

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

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

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

Объяснение

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

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

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

Реализация

Мы создадим вспомогательную функцию 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 i.e.
    # 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 раз. Поэтому общая временная сложность алгоритма HeapSort составляет 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)) .

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

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

Объяснение

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

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

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

Реализация

# 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) .

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

При хорошем повороте функция QuickSort разделила бы массив на половинки, которые логарифмически растут с 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 в Правда :

# 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() может сортировать любой итеративный объект, включая списки, строки, кортежи, словари, наборы и пользовательские итераторы , которые вы можете создать.

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

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

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

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

1 0.04006 0.02619 0.01639 5.53188 1.60355 1.23152
2 0.03999 0.02584 0.01661 4.92176 1.59103 1.24728
3 0.04407 0.02862 0.01646 4.91642 1.59362 1.22440
4 0.04128 0.02882 0.01860 5.15470 1.63463 1.25053
5 0.04515 0.03314 0.01885 4.95522 1.61759 1.28987
6 0.04257 0.02595 0.01628 5.04907 1.62515 1.25466
7 0.04028 0.02733 0.01760 5.05591 1.61981 1.24911
8 0.04264 0.02633 0.01705 5.08799 1.62603 1.25808
9 0.04302 0.03293 0.01762 5.03289 1.61446 1.24915
10 0.03966 0.02572 0.01606 5.14292 1.57273 1.22021
Avg 0.04187 0.02809 0.01715 5.08488 1.60986 1.24748

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

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

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

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

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

Вывод

Алгоритмы сортировки дают нам много способов упорядочить наши данные. Мы рассмотрели 6 различных алгоритмов – Bubble Sort, Selection Sort, Insert Sort, Merge Sort, HeapSort, QuickSort – и их реализации в Python.

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