Changeset 1584

Timestamp:

12/17/2007 09:32:03 PM (13 months ago)

Author:

zombor

Message:

Add sorting parameter to binary_search(), and add bubble, insertion, and quick sorts

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)
          * @return integer
          */
-        public function binary_search($needle, $haystack, $nearest = FALSE)
-        {
+        public function binary_search($needle, $haystack, $nearest = FALSE, $sort = FALSE)
+        {
+                if ($sort != FALSE AND is_string($sort))
+                {
+                        $method = $sort.'_sort';
+                        self::$method($haystack);
+                }
+
                 $high = count($haystack);
                 $low = 0;
@@ -118 +125 @@
                         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