Location: PHPKode > scripts > Class: Sort > class.sort.php
<?php
class sort {
/*
 * Sorting-algorithms implemented in PHP
 * 
 * A class that contains various sort-algorithms implemented in PHP
 * Copyright (C) 2008 Gustav Eklundh <hide@address.com>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 *
 * Current version: 1.0
 * Number of algos: 11
*/

#----[ Functions ]----#

	//------------------------------------------------------------
	// Private functions that is used along with the sorting-algos
	//------------------------------------------------------------

	private function array_swap(&$arr1, &$arr2) {
	# Implementation of the C++ function std::swap()
	# for making easier swaps.
		$tmp = $arr1;
		$arr1 = $arr2;
		$arr2 = $tmp;
	}
	
	private function sift(&$arr, $l, $r) {
	# Used together with the heap_sort function.
	# $a is used by reference, no return needed.
		$n = $l*2;
		$t = $arr[$l];
 		while($n <= $r) {
			if($n < $r && $arr[$n] < $arr[$n+1])
			$n++;
			if($t >= $arr[$n]) {
				$arr[$l] = $t;
				break;
			}
			$arr[$l] = $arr[$n];
			$l = $n;
			$n = 2*$l;
		}
		$arr[$l] = $t;
	}
	
	private function merge($l, $r) {
	# Used along with the mergesort-function
		$lc = $rc = $mc = $res = 0;
		$cl = count($l);
		$cr = count($r);
		while($lc < $cl && $rc < $cr) {
			if($l[$lc] < $r[$rc]) {
				$res[$mc++] = $l[$lc++];
			}
			else {
				$res[$mc++] = $r[$rc++];
			}
		}
		$cl_t = count($l);
		while($lc < $cl_t) {
			$res[$mc++] = $l[$lc++];
		}
		$cr_t = count($r);
		while($rc < $cr_t) {
			$res[$mc++] = $r[$rc++];
		}
		return $res;
	}
	
	private function reheap($arr, $len, $i) {
	# Used with JSort
		$done = false;
		$tmp = $arr[$i];
		$prnt = $i;
		$chld = 2*($i+1)-1;
		while(($chld < $len) && $done != true) {
			if($chld < $len-1) {
				if($arr[$chld] >= $arr[$chld+1]) {
					++$chld;
				}
			}
			if($tmp < $arr[$chld]) {
				$done = true;
			}
			else {
				$arr[$prnt] = $arr[$chld];
				$prnt = $chld;
				$chld = 2*($prnt+1)-1;
			}
		}
		$arr[$prnt] = $tmp;
		return $arr;		
	}
	
	private function invreheap($arr, $len, $i) {
	# Used with JSort
		$done = false;
		$tmp = $arr[$i];
		$prnt = $i;
		$chld = 2*($i+1)-1;
		while(($chld < $len) && $done != true) {
			if($chld < $len-1) {
				if($arr[$len-1-$chld] <= $arr[$len-1-($chld+1)]) {
					++$chld;
				}
			}
			if($tmp > $arr[$len-1-$chld]) {
				$done = true;
			}
			else {
				$arr[$len-1-$prnt] = $arr[$len-1-$chld];
				$prnt = $chld;
				$chld = 2*($prnt+1)-1;
			}
		}
		$arr[$len-1-$prnt] = $tmp;
		return $arr;
	}
	
	private function newGap($gap) {
	# newGap is used along with combsort for
	# fixing the gaps.
		$gap = ($gap*10)/13;
		if($gap == 9 || $gap == 10) {
			$gap = 11;
		}
		if($gap < 1) {
			$gap = 1;
		}
		return $gap;
	}
	
	//--------------------
	// Start of algorithms
	//--------------------
	
	public function bubble_sort($arr) {
	# The easiest and most ineffective sorting-algo
	# out there, not really useful for anything :)
		$h = null;
		$n = count($arr);
		for($i = 0; $i < $n; ++$i) {
			for($j = 0; $j < $n; ++$j) {
				if($arr[$i] < $arr[$j]) {
					$h = $arr[$i];
					$arr[$i] = $arr[$j];
					$arr[$j] = $h;
				}
			}
		}
			return $arr;
	}

	public function bibubble($arr) {
	# Bidirectional Bubble Sort, which differs a bit from
	# ordinary bubble sort since it's going both backwards
	# and forwards.
		$i = null;
		$limit = count($arr);
		$st = -1;
		while($st < $limit) {
			$f = false;
			++$st;
			--$limit;
			for($i = $st; $i < $limit; ++$i) {
				if($arr[$i] > $arr[$i+1]) {
					$tmp = $arr[$i];
					$arr[$i] = $arr[$i+1];
					$arr[$i+1] = $tmp;
					$f = true;
				}
			}
			if($f != true) {
				break;
			}
			for($i = $limit; --$i >= $st;) {
				if($arr[$i] > $arr[$i+1]) {
					$tmp = $arr[$i];
					$arr[$i] = $arr[$i+1];
					$arr[$i+1] = $tmp;
					$f = true;					
				}
			}
			if($f != true) {
				break;
			}
		}
		return $arr;
	}
	
	public function heap_sort($arr) {
	# The heap sort algo works by "heapifying"
	# the stack before sorting things out.
	# One of the fastest of the implementations
	# so far (v0.8).
		$t = null;
		$r = count($arr)-1;
		$l = (int)($r/2)+1;
		while($l > 0) {
			--$l;
			self::sift($arr, $l, $r);
		}
		while($r > 0) {
			$t = $arr[0];
			$arr[0] = $arr[$r];
			$arr[$r] = $t;
			--$r;
			self::sift($arr, $l, $r);
		}
		return $arr;
	}

	public function quicksort($arr) {
	# Raw php-implementation of quicksort
	# I suggest that you stick with sort() if
	# you're going to use quicksort in your code.
		if(!isset($arr[2])) {
			return $arr;
		}
		$piv = $arr[0];
		$x = $y = array();
		$len = count($arr);
		$i = 1;
		while($i < $len) {
			if($arr[$i] <= $piv) {
				$x[] = $arr[$i];
			}
			else {
				$y[] = $arr[$i];
			}
			++$i;
		}
		return array_merge(self::quicksort($x), array($piv), self::quicksort($y));
	}
	
	public function gnomesort($arr) {
	# Gnomesort implemented in PHP
	# It's a rather slow algo
		$len = count($arr);
		$i = 1;
		while ($i <= $len) {
			if($i == 0 || $arr[$i-1] <= $arr[$i]) {
				++$i;
			}
			else {
				$tmp = $arr[$i];
				$arr[$i] = $arr[$i-1];
				$arr[$i-1] = $tmp;
				--$i;
				if($i == 0) {
					$i == 1;
				}
			}
		}
		return $arr;
	}
	
	public function strand_sort($arr) {
	# Strand-sort is a sort-function
	# I guess.
		$r = array();
		while(count($arr)) {
			$sub = array();
			$sub[] = array_shift($arr);
			$l = count($sub)-1;
			foreach($arr as $k => $v) {
				if($v > $sub[$l]) {
					$sub[] = $v;
					unset($arr[$k]);
					++$l;
				}
			}
			if(!empty($r)) {
				foreach($sub as $v) {
					$s = false;
					foreach($r as $k => $rv) {
						if($v < $rv) {
							array_splice($r, $k, 0, $v);
							$s = true;
							break;
						}
					}
					if($s === false) {
						$r[] = $v;
					}
				}
			}
			else {
				$r = $sub;
			}
		}
		return $r;
	}
	
	public function mergesort($arr) {
	# Mergesort in PHP
	# Needs self::merge. The algo is also
	# recursive which makes it quite fast.
		$sl = round((count($arr)/2));
		$sr = count($arr)-$sl;
		$l = array_slice($arr, 0, $sl);
		$r = array_slice($arr, $sl);
		
		if($sl > 1) {
			$l = self::mergesort($l);
		}
		if($sr > 1) {
			$r = self::mergesort($r);
		}
		$res = self::merge($l, $r);
		return $res;
		
	}

	public function bogosort($arr) {
	# The most awsome sort-algo out there.
	# If it was to be explained with a card-deck, it
	# works like this: You take the deck, throws it
	# into the air and then just picks up the cards
	# randomly until they're sorted.
		$rnd = mt_rand();
		$len = count($arr);
		$sorted = false;
	
		do {
			$sorted = true;
			for($i = 0; $i < $len-1;++$i) {
				if($arr[$i] > $arr[$i+1]) {
					$sorted = false;
					break;
				}
			}
			if($sorted == false) {
				for($i = $len-1; $i > 0; --$i) {
					$rnd = mt_rand(0, $i);
					$tmp = $arr[$i];
					$arr[$i] = $arr[$rnd];
					$arr[$rnd] = $tmp;
				}
			}
		} while($sorted == false);
		return $arr;
	}
	
	public function jsort($arr) {
	# JSort builds a heap twice to order the array
	# before finishing of the sort with an insertion sort.
		$len = count($arr);
		for($i = $len-1; $i >= 0; --$i) {
			self::reheap($arr, $len, $i);
		}
		for($i = $len-1; $i >= 0; --$i) {
			self::invreheap($arr, $len, $i);
		}
		for($j = 1; $j < $len; ++$j) {
			$tmp = $arr[$j];
			$i = $j-1;
			while($i >= 0 && $arr[$i] > $tmp) {
				$arr[$i+1] = $arr[$i];
				--$i;
			}
			$arr[$i+1] = $tmp;
		}
		return $arr;
	}
	
	public function insertionSort($arr) {
	# Insertionsort is useful when you're about
	# to sort smaller arrays/lists, but it's not
	# that efficient when it comes to larger arrays/lists.
	# For that, quicksort, mergesort or heapsort is better.
		$len = count($arr);
		$tmp = null;
		$j = null;
		for($i=1; $i < $len;++$i) {
			$tmp = $arr[$i];
			$j = $i;
			while($j > 0 && $arr[$j-1] > $tmp) {
				$arr[$j] = $arr[$j-1];
				--$j;
			}
			$arr[$j] = $tmp;
		}
		return $arr;
	}
		
	public function combsort($arr) {
	# Combsort is a tweaked bubble sort which
	# performs much better.
	# A C++ comparision between Quicksort and Combsort
	# shows that Combsort takes just 1.1 times longer
	# than quicksort. More information:
	# http://www.yagni.com/combsort/index.php#cpp-combsort
		$gap = count($arr);
		$len = $gap;
		$swapped = true;
		while($gap != 1 && $swapped == true) {
			$gap = self::newGap($gap);
			$swapped = false;
			for($i=0;$i <= $len-$gap;++$i) {
				$j = $i+$gap;
				if($arr[$i] > $arr[$j]) {
					self::array_swap($arr[$i],$arr[$j]);
					$swapped = true;
				}
			}
		}
		return $arr;
	}

# End of class
}
?>
Return current item: Class: Sort