Home > Sort algorithms > Insertion Sort algorithm – PHP implementation

Insertion Sort algorithm – PHP implementation

Algorithm:

  1. Remove the element from the input array.
  2. Check to the left where is correct position for this element and move all elements to right with one step if those are bigger than element
  3. Insert the element in correct position

Insertion sort is very similar to selection sort. As in selection sort, after k passes through the array, the first k elements are in sorted order. For selection sort these are the k smallest elements, while in insertion sort they are whatever the first k elements were in the unsorted array. Insertion sort’s advantage is that it only scans as many elements as needed to determine the correct location of the (k+1)st element, while selection sort must scan all remaining elements to find the absolute smallest element.
However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems.
Performance:

  • Worst case: O(n2)
  • Average case: O(n2)
  • Best case: O(n)

PHP implementation (function from a larger sort Class):

     /**Function for sorting an array with insertion sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function insertionSort(array $array) {
        $length=count($array);
        for ($i=1;$i<$length;$i++) {
            $element=$array[$i];
            $j=$i;
            while($j>0 && $array[$j-1]>$element) {
                //move value to right and key to previous smaller index
                $array[$j]=$array[$j-1];
                $j=$j-1;
                }
            //put the element at index $j
            $array[$j]=$element;
            }
        return $array;
    }

Bibliography:

  1. Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  2. Algorithms – Robert Sedgewick
  3. http://en.wikipedia.org/wiki/Insertion_sort
Advertisements
Categories: Sort algorithms Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: