Archive

Archive for November, 2012

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

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