Алгоритм поиска и сортировки PHP: Shell sort

Алгоритм поиска и сортировки PHP: упражнение 5 с решением

Напишите программу PHP для сортировки списка элементов, используя сортировку Shell.

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

Пример запуска Shellsort с пробелами 5, 3 и 1 показан ниже.

Первый проход, 5-сортировка, выполняет сортировку вставки на отдельных подмассивах (a1, a6, a11), (a2, a7, a12), (a3, a8), (a4, a9), (a5, a10). Например, он изменяет подмассив (a1, a6, a11) с (62, 17, 25) на (17, 25, 62). Следующий проход, сортировка 3, выполняет сортировку вставки для подмассивов (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, a12). Последний проход, 1-сортировка, является обычной сортировкой вставки всего массива (a1, ..., a12). Как показано в примере, подмассивы, на которых работает Shellsort, изначально короткие; позже они длиннее но почти заказаны. В обоих случаях сортировка вставок работает эффективно. Сортировка оболочки нестабильна: она может изменить относительный порядок элементов с равными значениями. Это адаптивный алгоритм сортировки, который выполняется быстрее при частичной сортировке входных данных.

Shell Sort

Shellsort с пробелами 23, 10, 4, 1 в действии .

Пример решения:

PHP-код:

<?php
function shell_Sort($my_array)
{
	$x = round(count($my_array)/2);
	while($x > 0)
	{
		for($i = $x; $i < count($my_array);$i++){
			$temp = $my_array[$i];
			$j = $i;
			while($j >= $x && $my_array[$j-$x] > $temp)
			{
				$my_array[$j] = $my_array[$j - $x];
				$j -= $x;
			}
			$my_array[$j] = $temp;
		}
		$x = round($x/2.2);
	}
	return $my_array;
}
 
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Original Array :\n";
echo implode(', ',$test_array );
echo "\nSorted Array\n:";
echo implode(', ',shell_Sort($test_array)). PHP_EOL;
?>

Пример вывода:

 Оригинальный массив:                                                    
3, 0, 2, 5, -1, 4, 1                                                
Сортированный массив:                                                      
-1, 0, 1, 2, 3, 4, 5 

Блок-схема:

Редактор кода PHP:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу PHP для сортировки списка элементов, используя сортировку Selection.
Далее: Напишите программу PHP для сортировки списка элементов, используя Bubble sort.