Insertion Sort algorithm – PHP implementation

November 26, 2012 Leave a comment

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: , ,

Selection Sort algorithm – PHP implementation

November 25, 2012 1 comment

Algorithm:

  1. Find the smallest element in array and swap it with element from first position.
  2. Repeat first step with second smallest element and swap with element from second position.
  3. Continue until array is sorted.

This is among the simplest of sorting method, and it will work very well for small files. Its running time is proportional with n2 (n is array length): the number of comparisons between array elements is about n2/2, since the outer loop (on i) is executed n times and the inner loop (on j) is executed about n/2 times on average.

Performance:

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

PHP implementation (function from a larger sort Class):

    /**Function for sorting an array with selection sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function selectionSort(array $array) {
        for ($i=0;$i<count($array);$i++) {
            $min=$i;
            $length=count($array);
            for ($j=$i+1;$j<$length;$j++) {
                if ($array[$j]<$array[$min]) {
                    $min=$j;
                }
            }
            $tmp=$array[$min];
            $array[$min]=$array[$i];
            $array[$i]=$tmp;
        }
        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/Selection_sort
Categories: Sort algorithms Tags: , ,

Bubble Sort algorithm – PHP implementation

November 25, 2012 Leave a comment

Algorithm:

  1. Compare each pair of adiacent elements from the beginning of an array and, if they are in reversed order, swap them.
  2. If at least one swap has be done repeat step 1.

Is one of the most inefficient algorithm.
Performance:

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

PHP implementation:

    /**Function for sorting an array with bubble sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function bubbleSort(array $array) {
        $swapped=true;
        $j=0;
        $length=count($array);
        while($swapped) {
            $swapped=false;
            $j++;
            $comp=$length-$j;
            for ($i=0;$i<$comp;$i++) {
                if ($array[$i]>$array[$i+1]) {
                    $tmp=$array[$i];
                    $array[$i]=$array[$i+1];
                    $array[$i+1]=$tmp;
                    $swapped=true;
                }
            }
        }
        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/Bubble_sort
Categories: Sort algorithms Tags: , ,