Wednesday, April 16, 2014

Linear sort for numbers in PHP

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Sorting numbers in a defined range 0 ... N-1 with no repeats
   Inspired from Programming Pearls : Jon Bentley
   O(n) linear cost.
   PHP does not support long bit arrays out of the box.
   Code assumption: 32-bits integer
 */
    $N = 1000000;
    $SHIFT = 5;
    $MASK  = 0x1f;
    $BITS  = 32;
    $TOPVAL = (1+$N/$BITS);
   
    function set (&$a, $i)
    {
       global $SHIFT;
       global $MASK;
      
       $shift = $i >> $SHIFT;   /* Which byte to set */
       $mask = $i & $MASK;      /* Which bit to set */
       $a[$shift] = $a[$shift] | (1 << $mask);
      
       return;
    }
   
    function get ($a, $i)
    {
       global $SHIFT, $MASK;
       return ( $a[$i >>$SHIFT] & (1 << ($i & $MASK)) );
    }
   
    function linearsort (array & $a)
    { 
        global $TOPVAL;
        $bitvec = [];
        $maxval = 0;
        $i = 0;
       
        for ($indx = 0; $indx < $TOPVAL ; $indx++)
        {
           $bitvec[$indx] = 0;
        }
       
       
        for ($indx = 0; $indx < count($a) ; $indx++)
        {
           if ($a[$indx] > $maxval) $maxval = $a[$indx];
              set($bitvec, $a[$indx]);
        }
         
        for ($indx = 0; $indx <= $maxval ; $indx++)
        {
           if (get($bitvec, $indx))
             $a[$i++] = $indx;
        }
    }

    $a = array(205, 10, 7, 5, 9, 8, 1, 2, 100);
    linearsort ($a);
    print_r ($a);
?>

No comments:

Post a Comment