Статьи

Алгоритм недели: сортировка слиянием

Февраль 26, 2019

В основном алгоритмы сортировки можно разделить на две основные группы: те, которые основаны на сравнениях, и те, которые не являются таковыми. Я уже писал о некоторых алгоритмах первой группы. Сортировка вставок, пузырьковая сортировка и сортировка оболочки основаны на модели сравнения. Проблема этих трех алгоритмов состоит в том, что их сложность составляет O (n 2 ), поэтому они очень медленные.

Так можно ли отсортировать список элементов, сравнивая их элементы быстрее, чем O (n 2 )? Ответ — да, и вот как мы можем это сделать.

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

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

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

обзор

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

Дело в том, что на каком-то этапе алгоритма у нас есть два отсортированных списка, и самое сложное — объединить их. Однако это не так сложно.
Мы можем начать сравнивать первые элементы списков и затем вытолкнуть меньшие из них обоих и поместить их в новый список, содержащий объединенный (отсортированный) массив.

Реализация

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

$input = array(6, 5, 3, 1, 8, 7, 2, 4);
 
function merge_sort($arr)  
{  
	if (count($arr) <= 1) {
		return $arr;  
	}
 
	$left = array_slice($arr, 0, (int)(count($arr)/2));  
	$right = array_slice($arr, (int)(count($arr)/2));  
 
	$left = merge_sort($left);  
	$right = merge_sort($right);  
 
	$output = merge($left, $right);  
 
	return $output;  
}  
 
 
function merge($left, $right)  
{  
	$result = array();  
 
	while (count($left) > 0 && count($right) > 0) {  
		if ($left[0] <= $right[0]) {  
			array_push($result, array_shift($left));  
		} else {  
			array_push($result, array_shift($right));  
		}  
	}  
 
	array_splice($result, count($result), 0, $left);  
	array_splice($result, count($result), 0, $right);  
 
	return $result;  
}  
 
// 1, 2, 3, 4, 5, 6, 7, 8
$output = merge_sort($input);

сложность

Здорово, что сложность сортировки слиянием составляет O (n * log (n)) даже в худшем случае! Обратите внимание, что даже сложность быстрой сортировки может быть O (n 2 ) в худшем случае. Таким образом, мы можем быть уверены, что сортировка слиянием очень стабильна, независимо от ввода.

Две причины, по которым сортировка слиянием полезна

1. Быстро независимо от ввода

Сортировка слиянием — отличный алгоритм сортировки, главным образом потому, что он очень быстрый и стабильный. Его сложность одинакова даже в худшем случае и составляет O (n * log (n)). Обратите внимание, что даже сложность быстрой сортировки в худшем случае составляет O (n 2 ), что при n = 20 примерно в 4,6 раза медленнее!

2. Простота реализации

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

Три причины, по которым сортировка слиянием бесполезна

1. Медленнее, чем алгоритмы, не основанные на сравнении

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

2. Сложно реализовать для начинающих

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

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

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

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

35
Share: