Автор оригинала: Olivera Popović.
Вступление
Сортировка слиянием – один из самых известных алгоритмов сортировки. Если вы изучаете информатику, то Merge Sort , наряду с QuickSort , вероятно, является первым эффективным алгоритмом сортировки общего назначения, о котором вы слышали. Это также классический пример категории алгоритмов ” разделяй и властвуй|.
Сортировка слиянием
Способ работы сортировки слиянием заключается в следующем:
Исходный массив делится на две примерно равные части. Если массив имеет нечетное число элементов, то одна из этих “половинок” на один элемент больше другой.
Подмассивы снова и снова делятся на половинки, пока вы не получите массивы, каждый из которых имеет только один элемент.
Затем вы объединяете пары одноэлементных массивов в двухэлементные массивы, сортируя их в процессе. Затем эти отсортированные пары объединяются в четырехэлементные массивы и так далее, пока вы не закончите сортировку исходного массива.
Вот визуализация сортировки слиянием:
Как вы можете видеть, тот факт, что массив не может быть разделен на равные половины, не является проблемой. 3 просто “ждет”, пока начнется сортировка.
Существует два основных способа реализации алгоритма сортировки слиянием, один из которых использует подход сверху вниз , как в приведенном выше примере, именно так чаще всего вводится сортировка слиянием.
Другой подход, т. е. снизу вверх , работает в противоположном направлении, без рекурсии (работает итеративно) – если наш массив имеет N элементов, мы делим его на N подмассивов одного элемента и сортируем пары соседних одноэлементных массивов, затем сортируем соседние пары двухэлементных массивов и так далее.
Примечание: Подход снизу вверх обеспечивает интересную оптимизацию, которую мы обсудим позже . Мы будем реализовывать подход сверху вниз , поскольку он проще и интуитивно понятен в сочетании с тем фактом, что нет реальной разницы между временной сложностью между ними без конкретной оптимизации.
Основная часть обоих этих подходов заключается в том, как мы объединяем (сливаем) два меньших массива в больший массив. Это делается довольно интуитивно, допустим, мы рассмотрим последний шаг в нашем предыдущем примере. У нас есть массивы:
А: 2 4 7 8
Б: 1 3 11
сортировка: пусто
Первое, что мы делаем, это смотрим на первый элемент обоих массивов. Мы находим тот, который меньше, в нашем случае это 1 , так что это первый элемент нашего отсортированного массива, и мы двигаемся вперед в массиве B :
А: 2 4 7 8
Б: 1 3 11
сортировка: 1
Затем мы рассмотрим следующую пару элементов 2 и 3 ; 2 меньше, поэтому мы помещаем его в наш сортированный массив и двигаемся вперед в массиве A . Конечно, мы не движемся вперед в массиве B и держим наш указатель на 3 для будущих сравнений:
А: 2 4 7 8
Б: 1 3 11
сортировка: 1 2
Используя ту же логику, мы проходим через все остальное и в конечном итоге получаем массив{1, 2, 3, 4, 7, 8, 11}.
Два особых случая, которые могут возникнуть:
- Оба подмассива имеют один и тот же элемент. Мы можем двигаться вперед в любом из них и добавить элемент в сортированный массив. Технически мы можем двигаться вперед в обоих массивах и добавлять оба элемента в сортированный массив, но это потребует особого поведения, когда мы встретим одни и те же элементы в обоих массивах.
- Мы “выбегаем” из элементов в одном подмассиве. Например, у нас есть массив с {1, 2, 3} и массив с {9, 10, 11}. Ясно, что мы пройдем через все элементы в первом массиве, не двигаясь вперед ни разу во втором. Всякий раз, когда у нас заканчиваются элементы в подмассиве, мы просто добавляем элементы второго один за другим.
Имейте в виду, что мы можем сортировать так, как хотим – этот пример сортирует целые числа в порядке возрастания, но мы можем так же легко сортировать в порядке убывания или сортировать пользовательские объекты.
Реализация
Мы будем реализовывать сортировку слиянием на двух типах коллекций – на массивах целых чисел (обычно используемых для введения сортировки) и на пользовательских объектах (более практичный и реалистичный сценарий).
Мы реализуем алгоритм сортировки слиянием с использованием подхода сверху вниз . Алгоритм выглядит не очень “красиво” и может сбивать с толку, поэтому мы подробно рассмотрим каждый шаг.
Сортировка Массивов
Давайте начнем с самого простого. Основная идея алгоритма состоит в том, чтобы разделить (суб)массивы на половинки и отсортировать их рекурсивно. Мы хотим продолжать делать это как можно больше, то есть до тех пор, пока не получим подмассивы, имеющие только один элемент:
def merge_sort(array, left_index, right_index):
if left_index >= right_index:
return
middle = (left_index + right_index)//2
merge_sort(array, left_index, middle)
merge_sort(array, middle + 1, right_index)
merge(array, left_index, right_index, middle)
Вызывая метод merge последним, мы удостоверяемся, что все деления произойдут до того, как мы начнем сортировку. Мы используем оператор // , чтобы явно указать, что нам нужны целочисленные значения для наших индексов.
Следующий шаг-это фактическая часть слияния через несколько шагов и сценариев:
- Создавайте копии наших массивов. Первый массив является подмассивом из
[left_index,..,middle]и второй из[middle+1,...,right_index] - Мы проходим через обе копии (отслеживая указатели в обоих массивах), выбираем меньший из двух элементов, которые мы сейчас рассматриваем, и добавляем их в наш отсортированный массив. Мы движемся вперед в любом массиве, из которого мы выбрали элемент, и вперед в отсортированном массиве независимо.
- Если у нас закончатся элементы в одной из наших копий – просто добавьте оставшиеся элементы в другой копии к отсортированному массиву.
Изложив наши требования, давайте продолжим и определим функцию merge() :
def merge(array, left_index, right_index, middle):
# Make copies of both arrays we're trying to merge
# The second parameter is non-inclusive, so we have to increase by 1
left_copy = array[left_index:middle + 1]
right_copy = array[middle+1:right_index+1]
# Initial values for variables that we use to keep
# track of where we are in each array
left_copy_index = 0
right_copy_index = 0
sorted_index = left_index
# Go through both copies until we run out of elements in one
while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):
# If our left_copy has the smaller element, put it in the sorted
# part and then move forward in left_copy (by increasing the pointer)
if left_copy[left_copy_index] <= right_copy[right_copy_index]:
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
# Opposite from above
else:
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
# Regardless of where we got our element from
# move forward in the sorted part
sorted_index = sorted_index + 1
# We ran out of elements either in left_copy or right_copy
# so we will go through the remaining elements and add them
while left_copy_index < len(left_copy):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
sorted_index = sorted_index + 1
while right_copy_index < len(right_copy):
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
А теперь давайте протестируем нашу программу:
array = [33, 42, 9, 37, 8, 47, 5, 29, 49, 31, 4, 48, 16, 22, 26] merge_sort(array, 0, len(array) -1) print(array)
И выход есть:
[4, 5, 8, 9, 16, 22, 26, 29, 31, 33, 37, 42, 47, 48, 49]
Сортировка Пользовательских Объектов
Теперь, когда у нас есть базовый алгоритм, мы можем взглянуть на то, как сортировать пользовательские классы. Мы можем переопределить __eq__ , _le__ , _ge__ и другие операторы, необходимые для этого.
Это позволяет нам использовать тот же алгоритм, что и выше, но ограничивает нас только одним способом сортировки наших пользовательских объектов, который в большинстве случаев не является тем, что мы хотим. Лучше всего сделать сам алгоритм более универсальным и вместо этого передать ему функцию сравнения.
Сначала мы реализуем пользовательский класс Car и добавим к нему несколько полей:
class Car:
def __init__(self, make, model, year):
self.make = make
self.model = model
self.year = year
def __str__(self):
return str.format("Make: {}, Model: {}, Year: {}", self.make, self.model, self.year)
Затем мы внесем несколько изменений в наши методы сортировки слиянием. Самый простой способ достичь того, чего мы хотим, – это использовать лямбда-функции . Вы можете видеть, что мы добавили только дополнительный параметр и соответственно изменили вызовы методов, и только еще одну строку кода, чтобы сделать этот алгоритм намного более универсальным:
def merge(array, left_index, right_index, middle, comparison_function):
left_copy = array[left_index:middle + 1]
right_copy = array[middle+1:right_index+1]
left_copy_index = 0
right_copy_index = 0
sorted_index = left_index
while left_copy_index < len(left_copy) and right_copy_index < len(right_copy):
# We use the comparison_function instead of a simple comparison operator
if comparison_function(left_copy[left_copy_index], right_copy[right_copy_index]):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
else:
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
while left_copy_index < len(left_copy):
array[sorted_index] = left_copy[left_copy_index]
left_copy_index = left_copy_index + 1
sorted_index = sorted_index + 1
while right_copy_index < len(right_copy):
array[sorted_index] = right_copy[right_copy_index]
right_copy_index = right_copy_index + 1
sorted_index = sorted_index + 1
def merge_sort(array, left_index, right_index, comparison_function):
if left_index >= right_index:
return
middle = (left_index + right_index)//2
merge_sort(array, left_index, middle, comparison_function)
merge_sort(array, middle + 1, right_index, comparison_function)
merge(array, left_index, right_index, middle, comparison_function)
Давайте протестируем или модифицируем алгоритм на нескольких экземплярах Car :
car1 = Car("Alfa Romeo", "33 SportWagon", 1988)
car2 = Car("Chevrolet", "Cruze Hatchback", 2011)
car3 = Car("Corvette", "C6 Couple", 2004)
car4 = Car("Cadillac", "Seville Sedan", 1995)
array = [car1, car2, car3, car4]
merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.year < carB.year)
print("Cars sorted by year:")
for car in array:
print(car)
print()
merge_sort(array, 0, len(array) -1, lambda carA, carB: carA.make < carB.make)
print("Cars sorted by make:")
for car in array:
print(car)
Мы получаем результат:
Cars sorted by year: Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988 Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Corvette, Model: C6 Couple, Year: 2004 Make: Chevrolet, Model: Cruze Hatchback, Year: 2011 Cars sorted by make: Make: Alfa Romeo, Model: 33 SportWagon, Year: 1988 Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Chevrolet, Model: Cruze Hatchback, Year: 2011 Make: Corvette, Model: C6 Couple, Year: 2004
Оптимизация
Теперь давайте рассмотрим разницу между сверху вниз и снизу вверх Сортировкой слиянием. Bottom-up работает как вторая половина подхода top-down , где вместо рекурсивного вызова сортировки по половинным подмассивам мы итеративно сортируем соседние подмассивы.
Одна вещь, которую мы можем сделать, чтобы улучшить этот алгоритм, – это рассмотреть сортированные куски вместо отдельных элементов, прежде чем разбивать массив.
Это означает, что, учитывая такой массив, как {4, 8, 7, 2, 11, 1, 3} , вместо того, чтобы разбить его на {4}, {8}, {7}, {2}, {11}, {1} ,{3} – он разделен на подмассивы, которые уже могут быть отсортированы: {4,8}, {7}, {2,11}, {1,3} , а потом сортировка.
С реальными данными у нас часто есть много таких уже отсортированных подмассивов, которые могут заметно сократить время выполнения сортировки слиянием.
Еще одна вещь, которую следует учитывать при сортировке слиянием, особенно в версии сверху вниз ,-это многопоточность. Сортировка слиянием удобна для этого, так как каждая половина может быть отсортирована независимо от своей пары. Единственное, в чем нам нужно убедиться, – это в том, что мы закончили сортировку каждой половины, прежде чем объединять их.
Однако сортировка слиянием относительно неэффективна (как во времени, так и в пространстве), когда речь заходит о меньших массивах, и часто оптимизируется путем остановки, когда мы достигаем массива из ~7 элементов, вместо того чтобы спускаться к массивам с одним элементом и вызывать сортировку вставки, чтобы отсортировать их вместо этого, прежде чем сливаться в больший массив.
Это происходит потому, что сортировка вставки очень хорошо работает с небольшими и/или почти отсортированными массивами.
Вывод
Сортировка слиянием-это эффективный алгоритм сортировки общего назначения. Главное его преимущество-надежная работа алгоритма и эффективность при сортировке больших массивов. В отличие от QuickSort, он не зависит от каких-либо неудачных решений, которые приводят к плохому времени выполнения.
Одним из главных недостатков является дополнительная память, которую Merge Sort использует для хранения временных копий массивов перед их объединением. Однако сортировка слиянием-отличный, интуитивно понятный пример, чтобы познакомить будущих инженеров-программистов с подходом “разделяй и властвуй” к созданию алгоритмов.
Мы реализовали сортировку слиянием как для простых целочисленных массивов, так и для пользовательских объектов с помощью лямбда-функции, используемой для сравнения. В конце были кратко обсуждены возможные варианты оптимизации для обоих подходов.