|
deep inside webpages
 


Implementing QuickSort in PHP

Quicksort is practically the fastest way to sort an
array
of data. PHP's
array
sorting function
sort()
uses QuickSort.

How Quick Sort works?

This is how QuickSort operates on a list of elements:
  1. Picks a data element (called pivot) from an
    array
    ;
  2. Makes a comparison of all other elements with the pivot;
  3. Creates two subsets, one with values smaller than the pivot and the other with larger values;
  4. Repeats the above steps recursively on all the subsets until all subsets are broken down to individual elements;
  5. Groups together all subsets to produce sorted array of data.
Although you have a a function
sort()
in PHP that can do
array
sorting by implementing QuickSort, yet the below function from WikiBooks can be helpful in understanding the process.
  1. function quicksort( $array ) {
  2.     if( count( $array ) < 2 ) {
  3.         return $array;
  4.     }
  5.     $left = $right = array( );
  6.     reset( $array );
  7.     $pivot_key  = key( $array );
  8.     $pivot  = array_shift( $array );
  9.     foreach( $array as $k => $v ) {
  10.         if( $v < $pivot )
  11.             $left[$k] = $v;
  12.         else
  13.             $right[$k] = $v;
  14.     }
  15.     return array_merge(quicksort($left), array($pivot_key => $pivot), quicksort($right));
  16. }
  17.  
  18. //Using quicksort()
  19. $array  = quicksort( $array );    //returns sorted array.
PHP Code

To do the above with
sort()
:
  1. sort( $array );    //returns true on success, false otherwise
PHP Code



  1. Fixed Length & Large Random Numbers with PHP
  2. Number-to-Word Conversion with PHP
  3. Insecure PHP Constants and Variables
  4. Faster Random Numbers with PHP
  5. Interesting Use of PHP Super Globals