Home > Sort algorithms > Improvement of Quicksort algorithm – PHP implementation

Improvement of Quicksort algorithm – PHP implementation

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