# 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.

**Visual Presentation : Insertion Sort**

A graphical example of insertion sort :

Animation Credits : Swfung8

**Sample Solution:**

**PHP Code :**

```
<?php
// Function to perform insertion sort on an array
function insertion_Sort($my_array)
{
// Iterate over each element in the array
for ($i = 0; $i < count($my_array); $i++) {
$val = $my_array[$i]; // Store the current element
$j = $i - 1; // Initialize index for the previous element
// Shift elements of my_array[0..i-1] that are greater than val
// to one position ahead of their current position
while ($j >= 0 && $my_array[$j] > $val) {
$my_array[$j + 1] = $my_array[$j];
$j--;
}
$my_array[$j + 1] = $val; // Place val at its correct position
}
return $my_array; // Return the sorted array
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "Original Array :\n";
echo implode(', ', $test_array); // Display original array
echo "\nSorted Array :\n";
print_r(insertion_Sort($test_array)); // Display sorted array
?>
```

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 )

**Explanation:**

In the exercise above,

- The code defines a function named "insertion_Sort()" which takes an array '$my_array' as input and returns the sorted array.
- Insertion Sort Algorithm:
- The function iterates over each element in the array using a for loop.
- For each element, it compares it with the elements before it and shifts the elements to the right until it finds the correct position to insert the current element.
- Once the correct position is found, it inserts the element into that position.
- Output:
- After sorting the array using the "insertion_Sort()" function, the code prints the original array and the sorted array using the 'echo' and "print_r()" functions respectively.
- Usage:
- The function is then called with an example array '$test_array' containing unsorted numbers.
- It prints the original array and the sorted array to the console.

**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.

**What is the difficulty level of this exercise?**

Test your Programming skills with w3resource's quiz.

**Weekly Trends and Language Statistics**- Weekly Trends and Language Statistics