Archive

Archive for December, 2012

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