PHP: insertion sort implementation

Insertion sort has one outer loop and one inner loop. The first element in the list is considered sorted, thus, the outer loop starts from the second element to the end of the list. The inner loop starts from the current index-1 of the outer loop, and going backwards of the already sorted list until index 0 and inserts the value of the current outer index to the correct position of the already sorted elements. Each outer loop will increase the number of already sorted elements by 1, since each outer loop will insert the next element into the correct position of the already sorted elements.

Here is an example of insertion sort in php

<?php
function insertionSort($data)
{
	$n=count($data);
	$next=null;
	for($i=1; $i<$n; $i++)//outer loop
	{
		$next=$data[$i];
		for($j=$i-1; $j>=0; $j--)//inner loop
		{
			if( $data[$j]>$next )//change > to < for descending order
			{
				$data[$j+1]=$data[$j];
			}
			else
			{
				break;
			}
		}
		$data[$j+1]=$next; // insert the next value to the correct postion of the already sorted elements

	}

	return $data;
}

echo implode(",",array(43,23,4,11,2,88,76,46));
echo "<br>";
echo implode(",",insertionSort(array(43,23,4,11,2,88,76,46)));

demo

Search within Codexpedia

Custom Search

Search the entire web

Custom Search