Insertion Sort In PHP

Udemy Generic 728x90

Objective

In this tutorial we will learn the concept of Insertion sort algorithm and process to implement them in PHP code.

 

Insertion Sort  is a simple algorithm that we use to sort a given sequence of n numbers mostly arrays. It is an efficient algorithm for sorting a small number of elements.

 The insertion sort algorithm is an algorithm that is used by people in their everyday life than other algorithms. Take playing cards as an example, we take one card at a time from the pack and insert it into the correct position in our hand. To find the correct position for a card, we compare it with each of the cards already present in hand.

 

Step 2

Algorithm

The concept behind the Insertion sort algorithm is that we remove elements from an unordered set one by one and then insert them into an ordered set in the correct position.

Assume we have two arrays :

  • An unsorted array of n elements as input.
  • A sorted array of input as output.

Now in the beginning, sorted array contains the first element of array and others will be in unsorted array. In each step, the algorithm will take the first element from unsorted array and insert it to correct position in sorted array. When all elements will be moved from unsorted to sorted array, algorithm will stop.

A simple example to illustrate how insertion sort works : 

Input : {5,2,6,8,4}.

Output : {2,4,5,6,8}.

 

Step 3

Complexity analysis

  • Best Case : O(n).
  • Average Case : O(n2).
  • Worst Case : O(n2). 

On average Insertion sort’s complexity is O(n2). Best case of Insertion sort comes while sorting an almost sorted arrays which is O(n).

From the point of view of practical application, average case complexity of the insertion sort is not so important as Insertion sort is mostly used in sorting of small arrays. While working with small arrays Insertion sort is one of the fastest algorithms, even faster than Quick sort.

 

Step 4

Insertion Sort properties

  • Implementation of Insertion sort is very simple.
  • Very much efficient for small data sets.
  • In practice Insertion sort is more efficient than most of the other simple quadratic (O(n2)) algorithms such as selection sort or bubble sort.
  • Its Stable, i.e, it does not change the relative order of element with same values.
  • In-place, i.e., it only requires a constant amount of additional memory, i.e., O(1).
  • Online, i.e., if a new element is added to list during sort then it will get sorted as others.

 

Step 5

PHP implementation of Insertion sort

 

<br />
&lt;?php</p>
<p>/*<br />
*Function for sorting an array with insertion sort algorithms<br />
*/</p>
<p>function sortInsertion($array) {</p>
<p>    $sortedArray = array();</p>
<p>    for ($i = 0 ; $i &lt; count($array); $i++) {</p>
<p>        $element = $array[$i];<br />
        $j = $i;</p>
<p>        while($j &gt; 0 &amp;&amp; $sortedArray[$j-1] &gt; $element) {</p>
<p>            $sortedArray[$j] = $sortedArray[$j-1];<br />
            $j = $j-1;<br />
        }&lt;<br />
        $sortedArray[$j] = $element;<br />
    }<br />
    return $sortedArray;<br />
}</p>
<p>$unsorted = [5,2,6,8,4];<br />
$val = sortInsertion($unsorted);<br />
print_r($val);</p>
<p>?&gt;</p>
<p>


Step 5.1

Output

Array ( [0] => 2 [1] => 4 [2] => 5 [3] => 6 [4] => 8 )

 

Step 6

Step wise explanation of above code

  1. We have a function named sortInsertion(), which takes an unsorted array as input.
  2. Now we will iterate through that unsorted array using for loop.
  3. Inside for loop,  we will take ith $element in each iteration and put it into sorted array() in its correct position,jth.
  4. Now to find correct position, while loop is implemented.
  5. while loop will check if $element is greater than ( j-1 )thelement in $sortedArray.
  6. If  the above condition is met then insert $element in $sortedArray at jthposition.
  7. If not, then compare it with ( j-2 )th in sorted array if greater then shift ( j-2 )th element to right and put $element in its place.
  8. If not then repeat the same procedure.
  9. After iteration is complete and final sorted array, algorithm will terminate.

 

Udemy Generic 728x90

Spread the word. Share this post!

  • Noah Ellman

    Just benchmarked your insertion sort versus php’s sort(), using with an array of 10,000 random numbers.
    insertion sort: 2306ms runtime
    builtin sort(): 2ms runtime

    This is probably just because PHP sort() is implemented in C, and so its always going to be faster.

    • Erasus

      PHP built-in sort function uses quicksort implementation and yes it’s implemented in C, quicksort is also a lot better option for large arrays.