Большинство основных методов сортировки, которые мы изучили, включают BubbleSort, SelectionSort и InsertionSort, время выполнения которых составляет O(n²). Это в основном из-за их вложенной структуры цикла. Следовательно, они неэффективны, когда речь идет о больших массивах.

Однако MergeSort и QuickSort имеют время выполнения O(nlogn).
Почему это так?

Примечание: временная сложность в наихудшем случае для QuickSort O(n²). Это происходит, когда мы выбираем опорную точку как наибольший или наименьший элемент на каждом шаге рекурсии.

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

Реализация сортировки слиянием:

# Main Function
def merge_sort(lst: list):
    if len(lst) < 2:
        return lst[:]
    else:
        mid = len(lst) // 2
        left_tree = merge_sort(lst[:mid])
        right_tree = merge_sort(lst[mid:])

    return _merge(left_tree, right_tree)


# Helper Function
def _merge(left_tree, right_tree):
    i = 0
    j = 0
    merged = []
    while i < len(left_tree) and j < len(right_tree):
        if left_tree[i] <= right_tree[j]:
            merged.append(left_tree[i])
            i = i + 1
        else:
            merged.append(right_tree[i])
            j = j + 1

    return merged + left_tree[i:] + right_tree[j:]

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

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

  1. Первой частью будет передача списка [6, 5, 12, 10, 9 , 1] в функцию merge_sort.
  2. Затем функция разбивается на две части: левую и правую. Это делается до тех пор, пока каждая часть списка не достигнет индивидуального значения. Как мы видим выше [6], [5], [12], [10], [9], [1]
  3. Затем значения отправляются в функцию _merge для сравнения и сортировки.
  4. Затем функция _merge возвращает отсортированный список. Это делается до тех пор, пока не будут сравнены два последних списка. Простой способ увидеть это: «вернуть список в том виде, в котором он был разбит. Однако на этот раз мы делаем это упорядоченно».
    Например: [6,5,12] разбивается на [6] и [5,12]. Поскольку 6 является индивидуальным значением, он просто возвращает 6. Однако [5,12] разбивается на [5] и [12]. Затем эти значения отправляются в функцию _merge, результатом которой будет [5, 12]. Затем мы сравним [6] (наше исходное левое значение) с правым значением [5, 12]. После того, как мы пропустим это через функцию _merge, мы получим [5, 6, 12].

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

Реализация быстрой сортировки:

def quick_sort(lst):
  if len(lst) < 2:
    return lst[:]
  else:
    pivot = lst[-1]
    smaller, bigger = _partition(lst[0:-1], pivot)
    smaller_sorted = quick_sort(smaller)
    large_sorted = quick_sort(bigger)
  return smaller_sorted + [pivot] + large_sorted

def _partition(lst, pivot):
  smaller = []
  bigger = []
  for i in lst:
    if i < pivot:
      smaller.append(i)
    else:
      bigger.append(i)
  return smaller,bigger

Функция быстрой сортировки работает очень уникальным образом. Мы берем случайное значение из списка, указанного в аргументе, и называем его pivot. Затем мы разделяем список на две части (меньше и больше). Меньшая часть — это список, состоящий из всех значений в списке, меньших, чем равные опорной точке. Большая часть прямо противоположна ему. Мы продолжаем повторять каждую часть таким же образом, пока не достигнем базового случая. Следовательно, используя эту концепцию поворота и рекурсии, мы сможем получить отсортированный список.

Пример: если мы работаем со списком [1,2,4,3,2,1,5,0,1,2]

  1. Нашим первым шагом в функции быстрой сортировки будет использование последнего элемента в качестве опорного. (Примечание: вы можете взять любой элемент в качестве опорного, как обсуждалось выше. Однако, согласно коду, написанному выше, мы возьмем последний элемент в качестве опорного.)
  2. Так как мы видим, что исходная точка теперь равна 2. Мы передаем опорную точку и остальные элементы в списке функции _partition. Затем функция разделяет элементы на меньший ([1,1,0,1]) и больший список ([2, 4, 3, 2, 2,5]) .
  3. Затем функция возвращает все меньший и больший список, что в конечном итоге приводит к его повторной рекурсии, как показано в smaller_sorted и bigger_sorted, где она будет выполнять аналогичные шаги. В конце у нас будет отсортированный список.

Ниже приведен пример реализации функций быстрой сортировки:

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