<?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
}
?>