Home > Sort algorithms > Shell Sort algorithm – PHP implementation

Shell Sort algorithm – PHP implementation

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