PHP Searching and Sorting Algorithm: Insertion sort

PHP Searching and Sorting Algorithm: Exercise-3 with Solution

Write a PHP program to sort a list of elements using Insertion sort.

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

Pictorial Presentation : Insertion Sort

A graphical example of insertion sort :

Animation Credits : Swfung8

Sample Solution :

PHP Code :

<?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));
?>

Sample Output:

Original Array :                                                    
3, 0, 2, 5, -1, 4, 1                                                
Sorted Array :                                                      
Array                                                               
(                                                                   
    [0] => -1                                                       
    [1] => 0                                                        
    [2] => 1                                                        
    [3] => 2                                                        
    [4] => 3                                                        
    [5] => 4                                                        
    [6] => 5                                                        
) 

Flowchart :

PHP Code Editor:

Have another way to solve this solution? Contribute your code (and comments) through Disqus.

Previous: Write a PHP program to sort a list of elements using Heap sort.
Next: Write a PHP program to sort a list of elements using Selection sort.