Home > Sort algorithms > Gnome Sort algorithm – PHP implementation

Gnome Sort algorithm – PHP implementation

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