Статьи

Алгоритм недели: Shell Sort

Октябрь 21, 2018

Сортировка вставок — это отличный алгоритм, потому что он очень интуитивно понятен и его легко реализовать, но проблема в том, что он делает много обменов для каждого «легкого» элемента, чтобы поместить его в нужное место. Таким образом, «легкие» элементы в конце списка могут сильно снизить производительность сортировки вставкой. Вот почему в 1959 году Дональд Шелл предложил алгоритм, который пытается преодолеть эту проблему путем сравнения пунктов списка, которые находятся далеко друг от друга.

Сортировка вставки против сортировки оболочки

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

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

Shell Sort

Мы начинаем сравнивать элементы с фиксированным промежутком, который становится меньше на каждой итерации, пока не достигнет 1.

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

Дело в том, что сортировка вставкой вообще не является эффективным алгоритмом сортировки, но в некоторых случаях, когда список почти отсортирован, это может быть весьма полезно. С помощью сортировки Shell, когда список сортируется по гэпу = i, он сортируется по каждому гэпу = j, где j <i, и это является его основным преимуществом.

Принципы сортировки оболочки

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

Как выбрать размер зазора

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

Последовательность оболочки

Дональд Шелл предлагает последовательность, которая следует формуле FLOOR (N / 2 k ), тогда для N = 1000 мы получаем следующую последовательность: [500, 250, 125, 62, 31, 15, 7, 3, 1]

Последовательность Shell Gap

Последовательность оболочки для N = 1000: (500, 250, 125, 62, 31, 15, 7, 3, 1)

Последовательность Пратта

Пратт предлагает другую последовательность, которая растет медленнее, чем последовательность Шелл. Он предлагает последовательные числа вида 2 p 3 q или [1, 2, 3, 4, 6, 8, 9, 12, …].

Pratt Gap Sequence

Последовательность Пратта: (1, 2, 3, 4, 6, 8, 9, 12, …)

Последовательность Кнута

Кнут, с другой стороны, предлагает свою собственную последовательность, следуя формуле (3 k — 1) / 2 или [1, 4, 14, 40, 121, …]

Последовательность Кнута

Последовательность Кнута: (1, 4, 13, 40, 121, …)

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

Реализация

Вот реализация Shell для сортировки на PHP с использованием последовательности пробелов Pratt. Дело в том, что для этого набора данных могут оказаться более подходящими другие последовательности разрывов.

$input = array(6, 5, 3, 1, 8, 7, 2, 4);
 
function shell_sort($arr)
{
	$gaps = array(1, 2, 3, 4, 6);
	$gap  = array_pop($gaps);
	$len  = count($arr);
 
	while($gap > 0)
	{
		for($i = $gap; $i < $len; $i++) {
 
			$temp = $arr[$i];
			$j = $i;
 
			while($j >= $gap && $arr[$j - $gap] > $temp) {
				$arr[$j] = $arr[$j - $gap];
				$j -= $gap;
			}
 
			$arr[$j] = $temp;
		}
 
		$gap = array_pop($gaps);
	}
 
	return $arr;
}
 
// 1, 2, 3, 4, 5, 6, 7, 8
shell_sort($input);

Этот код легко изменить для работы с последовательностью оболочки.

$input = array(6, 5, 3, 1, 8, 7, 2, 4);
 
function shell_sort($arr)
{
        $len  = count($arr);
	$gap  = floor($len/2);
 
	while($gap > 0)
	{
		for($i = $gap; $i < $len; $i++) {
 
			$temp = $arr[$i];
			$j = $i;
 
			while($j >= $gap && $arr[$j - $gap] > $temp) {
				$arr[$j] = $arr[$j - $gap];
				$j -= $gap;
			}
 
			$arr[$j] = $temp;
		}
 
		$gap = floor($gap/2);
	}
 
	return $arr;
}
 
// 1, 2, 3, 4, 5, 6, 7, 8
shell_sort($input);

сложность

И снова мы не можем определить точную сложность этого алгоритма, потому что он зависит от последовательности пробелов. Однако мы можем сказать, какова сложность сортировки Шелла с последовательностями Кнута, Пратта и Дональда Шелла. Для последовательности Шелла сложность O (n 2 ), а для последовательности Пратта — O (n * log 2 (n)). Наилучшим подходом является последовательность Кнута, где сложность O (n 3/2 ), как вы можете видеть на диаграмме ниже.

Сложность Shell Sort

Сложность сортировки Shell с различными последовательностями пробелов.

заявка

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

Похожие сообщения:

  1. Компьютерные алгоритмы: сортировка вставок
  2. Компьютерные алгоритмы: Bubble Sort
  3. Пятничные алгоритмы: JavaScript Bubble Sort

Вы отличный разработчик? Нажмите здесь, чтобы узнать, сколько!

Источник: http://www.stoimen.com/blog/2012/02/27/computer-algorithms-shell-sort/

51
Share: