Changeset 1585

Timestamp:

12/17/2007 10:26:14 PM (11 months ago)

Author:

zombor

Message:

removing the hand coded search functions...built in sort() is 400x faster than a hand build merge sort.

Files:

• trunk/system/helpers/arr.php (modified) (2 diffs)

trunk/system/helpers/arr.php

@@ -84 +84 @@
          * @param  array    an array of values to search in
          * @param  boolean  return false, or the nearest value
-         * @param  mixed    sort the array by the requested sorting method (available types are bubble, insertion, quick, selection, merge)
+         * @param  mixed    sort the array before searching it
          * @return integer
          */
         public function binary_search($needle, $haystack, $nearest = FALSE, $sort = FALSE)
         {
-                if ($sort != FALSE AND is_string($sort))
+                if ($sort)
                 {
-                        $method = $sort.'_sort';
-                        self::$method($haystack);
+                        sort($haystack);
                 }
 
@@ -125 +124 @@
                         return $high;
         }
-
-        /**
-         * Bubble sort algorithm.
-         *
-         * @param  array the array to sort
-         */
-        public function bubble_sort(&$array)
-        {
-                $size = count($array);
-                do
-                {
-                        $swapped = FALSE;
-                        $size--;
-                        for ($i = 0; $i < $size; $i++)
-                        {
-                                if ($array[$i] > $array[$i+1])
-                                {
-                                        // Swap the values
-                                        $temp = $array[$i+1];
-                                        $array[$i+1] = $array[$i];
-                                        $array[$i] = $temp;
-                                        $swapped = TRUE;
-                                }
-                        }
-                } while ($swapped);
-        }
-
-        /**
-         * Insertion sort algorithm.
-         *
-         * @param  array the array to sort
-         */
-        public function insertion_sort(&$array)
-        {
-                for ($i = 0; $i < count($array); $i++)
-                {
-                        $value = $array[$i];
-                        $j = $i - 1;
-                        while ($j >= 0 AND $array[$j] > $value)
-                        {
-                                $array[$j+1] = $array[$j];
-                                $j--;
-                        }
-                        $array[$j+1] = $value;
-                }
-        }
-
-        /**
-         * Quick sort algorithm.
-         *
-         * @param  array the array to sort
-         * @param  integer low position to start at
-         * @param  integer high position to start at
-         * @param  integer minumum number of items to sort. If below the value, we go to insertion sort since its faster on small datasets
-         */
-        public function quick_sort(&$array, $low_pos, $high_pos, $cutoff = 1500)
-        {
-                // Quick sort is actually slow on small data sets
-                if($low_pos + $cutoff > $high_pos)
-                { 
-                        self::insertion_sort($array); 
-                }
-                else
-                {
-                        $left = $low_pos;
-                        $right = $high_pos;
-                        $pivot = $array[$left];
-                        while ($left < $right)
-                        { 
-                                while (($array[$right] >= $pivot) && ($left < $right))
-                                {
-                                        $right--;
-                                } 
-                                if ($left != $right)
-                                {
-                                        $array[$left] = $array[$right];
-                                        $left++;
-                                }
-                                while (($array[$left] <= $pivot) && ($left < $right)) 
-                                {
-                                        $left++; 
-                                        if ($left != $right)
-                                        { 
-                                                $array[$right] = $array[$left]; 
-                                                $right--; 
-                                        } 
-                                } 
-                                $array[$left] = $pivot; 
-                                $pivot = $left; 
-                                if ($low_pos < $pivot)
-                                {
-                                        self::qsort($array, $low_pos, $pivot, $cutoff);
-                                }
-                                if ($high_pos > $pivot)
-                                {
-                                        self::qsort($array, $pivot+1, $high_pos, $cutoff); 
-                        }
-                        }
-                }
-        }
-
-        /**
-         * Selection sort algorithm.
-         *
-         * @param  array the array to sort
-         */
-        public function selection_sort(&$array)
-        {
-                
-        }
-
-        /**
-         * Merge sort algorithm.
-         *
-         * @param  array the array to sort
-         */
-        public function merge_sort(&$array)
-        {
-                
-        }
 } // End arr