Registreren

[RedRose]

Inleiding
Het QuickSort algoritme is een zeer snel sorteringsalgoritme. In dit artikel zal ik twee voorbeelden van implementatie geven; in Java en PHP.

JAVA

Code: Alles selecteren

/**
* Swap positions a and b in given array.
* @param n Array with values.
* @param a First position.
* @param b Second position.
* @author Jorn van der Pol
*/
void swap( int n[], int a, int b )
{
   int T = n[ a ];
   n[ a ] = n[ b ];
   n[ b ] = T;
}

/**
* QuickSort array values. Start with very left position and very right position within this array.<br>
* Should be called like this:<br>
* int values[] = {3, 1, 2};<br>
* quicksort( values, 0, 3 );<br>
* @param values The values to sort.
* @param begin very left position within values[].
* @param end very right position within values[].
* @author Jorn van der Pol
*/
void quicksort( int values[], int begin, int end )
{
   // Set searchpositions.
   int left = begin;
   int right = end;
   
   // Select pivot value.
   int pivot = values[ ( begin + end ) / 2 ];
   
   // While left position <= right position.
   do
   {
      // Search first value greater than or equal to pivot value.
      while( values[ left ] < pivot )
         left++;
     
      // Search last value less than or equal to pivot value.
      while( values[ right ] > pivot )
         right--;
     
      if( left <= right )
      {
         // Swap values.
         swap( values, left, right );
         
         // Move positions.
         left++;
         right--;
      }
   }
   while( left <= right );
   
   // Sort lower part and upper part.
   if( begin < right )
      quicksort( values, begin, right );
   if( left < end )
      quicksort( values, left, end );
}

PHP

Code: Alles selecteren

/**
* Swap positions a and b in given array.
* @param values Array with values.
* @param a First position.
* @param b Second position.
* @author Jorn van der Pol
*/
function swap( &$values, $a, $b )
{
   $T = $values[ $a ];
   $values[ $a ] = $values[ $b ];
   $values[ $b ] = $T;
}
 
/**
* QuickSort array values. Start with very left position and very right position within this array.<br>
* Should be called like this:<br>
* $values = array( 3, 1, 2 );<br>
* quicksort( values, 0, 3 );<br>
* @param values The values to sort.
* @param begin very left position within values[].
* @param end very right position within values[].
* @author Jorn van der Pol
*/
function quicksort( &$values, $begin, $end )
{
   // Set searchpositions.
   $left = $begin;
   $right = $end;
   
   // Select pivot value.
   $pivot = $values[ ( $begin + $end ) / 2 ];
   
   // While left position <= right position.
   do
   {
      // Search first value greater than or equal to pivot value.
      while( $values[ $left ] < $pivot )
         $left++;
      
      // Search last value less than or equal to pivot value.
      while( $values[ $right ] > $pivot )
         $right--;
      
      if( $left <= $right )
      {
         // Swap values.
         swap( $values, $left, $right );
         
         // Move positions.
         $left++;
         $right--;
      }
   }
   while( $left <= $right );
   
   // Sort lower part and upper part.
   if( $begin < $right )
      quicksort( $values, $begin, $right );
   if( $left < $end )
      quicksort( $values, $left, $end );
}