Merge sort algorithm – PHP implementation

December 31, 2012 Leave a comment

Heapsort is a divide and conquer algorithm that was invented by John von Neumann in 1945.
Algorithm:

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sublists until there is only 1 sublist remaining. This will be the sorted list.

Performance:

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

PHP implementation (a special class for merge sorting):

 
class mergeSort {
    /**
     * splitting the array recursively until has max two elements
     * merging and sorting recursively until sorted array is built
     * 
     * @param type $array
     * @return array Sorted input array
     */
    public function sort($array) {
        //if array has 1 element return that element
        $count=count($array);
        if ($count<=1)
            return $array;
        //split array and build left and right arrays
        $mid=(int)$count/2;
        $left=array();
        $right=array();
        for ($i=0;$i<$mid;$i++) {
            $left[]=$array[$i];
        }
        for ($i=$mid;$imerge($this->sort($left),$this->sort($right));
    }
    /**
     * merge left and right arrays sorting elements
     * 
     * @param array $left
     * @param array $right
     * @return array
     */
    private function merge($left,$right) {
        $sorted=array();
        //compare first element from left with first element from right
        //add the lowest to $sorted and erase it from parent array
        while (count($left)>0 && count($right)>0) 
            if ($left[0]<$right[0]) {
                $sorted[]=$left[0];
                array_shift($left);
            } else {
                $sorted[]=$right[0];
                array_shift($right);
            }
        //after one of right and left arrays is empty is added elements from
        //remaining to $sorted
        for ($i=0;$i<count($left);$i++) 
            $sorted[]=$left[$i];
        for ($i=0;$i<count($right);$i++) 
            $sorted[]=$right[$i];
        return $sorted;
    }
}

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/Merge_sort
Categories: Sort algorithms Tags: , ,

Heapsort algorithm – PHP implementation

December 5, 2012 Leave a comment

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family.
Algorithm:

  1. Build a heap (heap is a tree structure with rule that parent value are bigger or equal with childrens values) out of the data.
  2. Removing the largest element from the heap and insert in sorted array starting with first position (0).
  3. Reconstruct the heap with remaining elements and add largest value in sorted array.

Heap sort can be performed in place by spliting the array in two parts, the heap and the sorted array.
Performance:

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

PHP implementation (a special class for heap sorting):

 
class heapSort {
    /**Change first value to the end of array recursively
     * 
     * @param array $array
     * @return array
     */
    public function heap(&$array) {
        $length=count($array);
        $this->heapify($array,$length);
        $end=$length-1;
        while ($end>0) {
            $tmp=$array[0];
            $array[0]=$array[$end];
            $array[$end]=$tmp;
            $end=$end-1;
            $this->siftDown($array,0,$end);
        }
        return $array;
    }
    /**Build binary tree 
     * 
     * @param array $array
     * @param integer $count
     */
    private function heapify(&$array,$count) {
        $start=floor(($count-2)/2);
        while ($start>=0) {
            $this->siftDown($array,$start,$count-1);
            $start=$start-1;
        }
    }
    /**Arrange tree branch: parent node bigger than his children
     * 
     * @param array $array
     * @param integer $start
     * @param integer $end
     * @return when tree is sorted
     */
    private function siftDown(&$array,$start,$end) {
        $root=$start;
        while ($root*2+1<=$end) {
            $left=$root*2+1;
            $swap=$root;
            //check who is the bigger between root,left child and right child
            if ($array[$swap]<$array[$left]){
                $swap=$left;
            } 
            if ($left+1<=$end && $array[$swap]<$array[$left+1]){
                $swap=$left+1;
            }
            //swap root with bigger children (if exist)
            if ($swap!=$root) {
                $tmp=$array[$root];
                $array[$root]=$array[$swap];
                $array[$swap]=$tmp;
                $root=$swap;
            } else return;
        }
    }
}

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/Heapsort
Categories: Sort algorithms Tags: , ,

Improvement of Quicksort algorithm – PHP implementation

November 28, 2012 Leave a comment

Because quicksort has bad performance on little arrays (or list) I used Insertion sort for arrays with fewer than 30 elements (I ran some tests and found that 30 is better than 20 or 40).

This improvement is faster with around  30-40%.

PHP implementation (function from a larger sort Class that use Insertion method discussed earlier):

 
    /**Function for sorting an array with optimized quick sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function optQuickSort(array $array) {
        if (count($array)<30) 
            return self::insertionSort($array);
        $low=array();
        $high=array();
        $length=count($array);
        $pivot=$array[0];
        for ($i=1;$i<$length;$i++) {
            if ($array[$i]<$pivot) {
                $low[]=$array[$i];
            } else {
                $high[]=$array[$i];
            }
        }
        return array_merge(self::optQuickSort($low),array($pivot),
                           self::optQuickSort($high));
    }
}

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/Quick_sort
Categories: Sort algorithms Tags: , ,

Quick Sort algorithm – PHP implementation

November 27, 2012 Leave a comment

Quicksort is a divide and conquer algorithm: recursively split a large array in two sub-arrays, one with low elements and second with high elements.
Algorithm:

  1. Pick an element, called pivot, from the list.
  2. Reorder hte list so the element with value less than pivot came before pivot, and elements higher came after the pivot.
  3. Recursively sort the sub-list of lower and higher elements.

This algorithm is used as built-in in PHP and in MySQL and is most widely used.
Performance:

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

PHP implementation (function from a larger sort Class):

 
     /**Function for sorting an array with quick sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function quickSort(array $array) {
        if (count($array)<2) 
            return $array;
        $low=array();
        $high=array();
        $length=count($array);
        $pivot=$array[0];
        for ($i=1;$i<$length;$i++) {
            if ($array[$i]<$pivot) {
                $low[]=$array[$i];
            } else {
                $high[]=$array[$i];
            }
        }
        return array_merge(self::quickSort($low),array($pivot),
                        self::quickSort($high));
    }

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/Quick_sort
Categories: Sort algorithms Tags: , ,

Gnome Sort algorithm – PHP implementation

November 27, 2012 Leave a comment

Algorithm:

  1. Finds the first place where two adiacent elements are in wrong order and swap them.
  2. Check to the left if there are wrong order of two adiacent elements and swap if found.
  3. If not found other elements on left continue with step 1.

Gnome sort is a sorting algorithm  which is similar to insertion sort, except that moving an element to its proper place is accomplished by a series of swaps, as in bubble sort.
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 gnome sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function gnomeSort(array $array) {
        $i=1;
        while($i<count($array)) {
            if ($array[$i]>=$array[$i-1]){
                $i++;
            } else {
                //swap the elements
                $tmp=$array[$i];
                $array[$i]=$array[$i-1];
                $array[$i-1]=$tmp;
                if ($i>1) {
                    $i--;
                }
            }
        }
        return $array;
    }

Bibliography:

  1. http://en.wikipedia.org/wiki/Gnome_sort
Categories: Sort algorithms Tags: , ,

Comb Sort algorithm – PHP implementation

November 27, 2012 Leave a comment

Algorithm:

  1. Compare each pair of elements found on positions n and n+gap and, if they are in reversed order, swap them.
  2. Change the step by division with 1.3
  3. If step is 1 do bubble sort

In bubble sort, when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1 (Shell sort is also based on this idea, but it is a modification of insertion sort rather than bubble sort).
Performance:

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

PHP implementation:

     /**Function for sorting an array with comb sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function combSort(array $array) {
        $swapped=false;
        $j=0;
        $length=count($array);
        $gap=$length;
        while($gap>1 || $swapped) {
            if ($gap>1) {
                $gap=floor($gap/1.2473);
            }
            $swapped=false;
            $j++;
            for ($i=0;$i+$gap<$length;$i++) {
                if ($array[$i]>$array[$i+$gap]) {
                    $tmp=$array[$i];
                    $array[$i]=$array[$i+$gap];
                    $array[$i+$gap]=$tmp;
                    $swapped=true;
                }
            }
        }
        return $array;
    }

Bibliography:

  1. http://en.wikipedia.org/wiki/Comb_sort
Categories: Sort algorithms Tags: , ,

Shell Sort algorithm – PHP implementation

November 27, 2012 Leave a comment

Algorithm:

  1. Remove the element from the input array at position h+n.
  2. Compare the element form position h+n with element from position n and switch if is smaller
  3. Continue with until finish the array and change to next gap

Shell sort is based on bubble sort and insertion sort but change to step for compare two elements of array. Practically is a multi-pass algorithm (because there are more steps): each pass is an insertion sort of the sequences consisting of every h-th element for a fixed gap h (also known as the increment).
Performance is depending of gap sequence used for sorting. I used next sequence: 701,301,132,57,23,10,4,1. Like an observation all gap must finish in 1.
Performance:

  • Worst case: depend on gap, no more than O(n2)
  • Average case: depend on gap, no more than O(n2)
  • Best case: depend on gap

PHP implementation (function from a larger sort Class):

     /**Function for sorting an array with shell sort algorithm.
     * 
     * @param array $array
     * @return array
     */
    public static function shellSort(array $array) {
        $gaps=array(701,301,132,57,23,10,4,1);
        $length=count($array);
        $lgap=count($gaps);
        for ($z=0;$z<$lgap;$z++) {
            $gap=$gaps[$z];
            for ($i=$gap;$i<$length;$i++) {
                $element=$array[$i];
                $j=$i;
                while($j>=$gap && $array[$j-$gap]>$element) {
                    //move value to right and key to previous smaller index
                    $array[$j]=$array[$j-$gap];
                    $j=$j-$gap;
                    }
                //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/Shell_sort
Categories: Sort algorithms Tags: , ,
Follow

Get every new post delivered to your Inbox.