Home > Sort algorithms > Quick Sort algorithm – PHP implementation

Quick Sort algorithm – PHP implementation

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