PHP Program - Insertion Sort

Insertion sort is based on the idea of consuming one element from unsorted array and inserting it at the correct position in the sorted array. This will result into increasing the length of the sorted array by one and decreasing the length of unsorted array by one after each iteration.

Example:

To understand the insertion sort, lets consider an unsorted array [23, 1, 10, 5, 2] and discuss each step taken to sort the array in ascending order. In every pass, one element is taken from the unsorted array and inserted it at the correct position in the sorted array.

First Pass: The whole array is unsorted array and (23) is taken to be inserted into the sorted array. As (23) is the first element of sorted array and has no elements to be compared with, it remains at its position.

Second Pass: (1) is the taken from unsorted array to insert into sorted array. It is compared with all elements of sorted array and found that (23) is the only number which is greater than (1). (1) is inserted into the sorted array and position of (23) is shifted by one place in the array. This resulted into increasing the length of sorted array by one and decreasing the length of unsorted array by one.

Third Pass: (10) is taken from the unsorted array and compared with all elements of sorted array. (23) is the only number in the sorted array which is greater than (10). (10) is inserted into the sorted array and position of (23) is shifted by one place in the array.

Fourth Pass: (5) is compared with all elements of sorted array and it is found that (10) and (23) are the numbers which need to be shifted by one place to insert (5) into the sorted array.

Fifth Pass: To insert (2) into the sorted array, (5), (10) and (23) are shifted by one place.

Implementation of Insertion Sort

<?php
// function for insertion sort
function insertionsort(&$Array, $n) {
  for($i=0; $i<$n; $i++) {
    $curr = $Array[$i];
    $j = $i - 1;
    while($j >= 0 && $curr < $Array[$j]) {
      $Array[$j + 1] = $Array[$j];
      $Array[$j] = $curr;
      $j = $j - 1;
    }
  }
}

// function to print array
function PrintArray($Array, $n) { 
  for ($i = 0; $i < $n; $i++) 
    echo $Array[$i]." "; 
  echo "\n";
} 

// test the code
$MyArray = array(1, 10, 23, 50, 4, 9, -4);
$n = sizeof($MyArray); 
echo "Original Array\n";
PrintArray($MyArray, $n);

insertionsort($MyArray, $n);
echo "\nSorted Array\n";
PrintArray($MyArray, $n);
?>

The above code will give the following output:

Original Array
1 10 23 50 4 9 -4 

Sorted Array
-4 1 4 9 10 23 50

Time Complexity:

Insertion sort takes maximum time if the array is in the reverse order and minimum time when the array is already sorted. In worst case scenario every element is compared with all other elements. Therefore, for N elements there will be N² comparison hence the time complexity of insertion sort is Θ(N²).