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

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

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

Вставка сортировки - это простой алгоритм сортировки, который создает окончательный отсортированный массив (или список) по одному элементу за раз. Он гораздо менее эффективен в больших списках, чем более продвинутые алгоритмы, такие как быстрая сортировка, heapsort или сортировка слиянием.

Иллюстрированная презентация: вставка сортировки

Графический пример вставки сортировки:

Кредиты на анимацию: Swfung8

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

PHP-код:

<?php
 function insertion_Sort($my_array)
{
	for($i=0;$i<count($my_array);$i++){
		$val = $my_array[$i];
		$j = $i-1;
		while($j>=0 && $my_array[$j] > $val){
			$my_array[$j+1] = $my_array[$j];
			$j--;
		}
		$my_array[$j+1] = $val;
	}
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";
print_r(insertion_Sort($test_array));
?>

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

 Оригинальный массив:                                                    
3, 0, 2, 5, -1, 4, 1                                                
Сортированный массив:                                                      
массив                                                               
(                                                                   
    [0] => -1                                                       
    [1] => 0                                                        
    [2] => 1                                                        
    [3] => 2                                                        
    [4] => 3                                                        
    [5] => 4                                                        
    [6] => 5                                                        
) 

Блок-схема:

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

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

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