Insertion Sort Program in PHP

Definition

Insertion Sort is basically insertion of an element from a random set of numbers, to its correct position where it should actually be, by shifting the other elements if required.

Insertion sort is a simple sorting algorithm that allows for efficient, in-place sorting of the array, one element at a time. By in-place sorting, we mean that the original array is modified and no temporary structures are needed.

Worst complexity: n^2
Average complexity: n^2
Best complexity: n
Space complexity: 1

Algorithm 
1. For k ← 2 to length [A]
2. Do key ← A[k]
3. i=k-1
4. while i>0 and A[i]>key
5. do A[i+1] ← A[i]
6. i=i-1
7. A[i+1] ← key

Program 

//Display Array
function display_array($array){
   $message = "";
   $len = count($array);
   for($i=0;$i<$len;$i++){
      $val = $array[$i];
      $message .= $val;
      $message .= ($i==$len-1)? ".":",";
   }
   return $message;
}
//Insertion Sort
function insertionSort($array) {
   $size = count($array);
   for ($step = 1; $step < $size; $step++) {
      $key = $array[$step];
      $j = $step-1;
      // Compare key with each element on the left of it until an element smaller than
      // it is found.
      // For descending order, change key<array[j] to key>array[j].
      while ($j >= 0 && $key < $array[$j]) {
         $array[$j + 1] = $array[$j];
         --$j;
      }
      $array[$j + 1] = $key;
   }
   return $array;
}
$array = [20,3,22,4,5,11,43,42,24,54];
echo "<p>".display_array($array)."</p>";
$display_array = insertionSort($array);
echo "<p>".display_array($display_array)."</p>";

Output

20,3,22,4,5,11,43,42,24,54.

3,4,5,11,20,22,24,42,43,54.

Space Complexity Analysis-

• It performs all computation in the original array and no other array is used.
• Selection sort is an in-place algorithm.

Important Notes-

• Insertion sort is not a very efficient algorithm when data sets are large.
• This is indicated by the average and worst case complexities.
• Insertion sort is adaptive and number of comparisons are less if array is partially sorted.