Home

Sort

Much better than quicksort!

Sun, 06/10/2007 - 12:50 | by Mgccl

Sorry, the title is misleading , I did not find some algorithm faster than quicksort, in fact, quicksort's lower bound is proven the lowest for any comparison sort algorithm.
Two days ago, a article about using quicksort algorithm in PHP by Tim Koschuetzki caught my eyes.

Koschuetzki was working on an array somewhat like this:

Array
(
    [0] => Array
        (
            [idv11] => 624059d1f8N0
            [adspots] => 2
    )
    [1] => Array
        (
            [idv11] => 67059d1f8N0
            [adspots] => 4
    )
    [2] => Array
        (
            [idv11] => 6759d1f8N0
            [adspots] => 8
    )
)

I took out all the unnecessary keys and values for ease of understanding.
Koschuetzki's goal is to sort the array by the adspots. Since it's a multidimensional array, he can't use sort() provided by PHP, so he creates his own code in PHP and improved his code from Θ(n^2) time into Θ(n log n) time. Good work, but there should be a better way.

Usually, problems like this are taking care by the database, I don't know why Koschuetzki's corporation ask the sorting to be done in PHP. So I come up with something extremely fast.

Below is the simplified version of Koschuetzki's quicksort. I created it by modifying the PHP quicksort implementation posted on wikibook.

function quicksort_by_adspots($array){
        if(!count($array)) return $array;
 
        $k = $array[0]['adspots'];
        $own = $array[0];
        $x = $y = array();
        $count = count($array);
        for($i=1; $i<$count; $i++)
        {
                if($array[$i]['adspots'] <= $k)
                {
                        $x[] = $array[$i];
                }
                else
                {
                        $y[] = $array[$i];
                }
        }
 
        return array_merge(quicksort_by_adspots($x), array($own), quicksort_by_adspots($y));
}

An array of 10000 values = 11 seconds!
Quicksort is fast, even PHP's internal is using quicksort. I believe Radix sort1 are the only generally acceptable faster sorting function. PHP, as ainterpreted language usually can't top other compiled languages.
So, I made a function do the same thing, but using usort().

function usort_by_adspots($array){
	function adcomp($a, $b){
	    if ($a['adspots'] == $b['adspots']) {
	        return 0;
	    }
	    return ($a['adspots'] < $b['adspots']) ? -1 : 1;
	}
	usort($array, "adcomp");
 
	return $array;
}

An array of 10000 values = 0.4 seconds!
Huge performance boost.

I guess this shows the importance of read the manual, I check out the entire manual and read each one of them today and finally found what I need. usort is the last array function in the manual.

  1. 1. LSD Radix sort is a stable sort with Θ(n·k/s) time and Θ(n) memory.
Tags:

PHP implementation of Pancake sort

Fri, 01/19/2007 - 11:24 | by Mgccl

PHP implementation of Pancake sort, the very mathy but slow(at least in PHP) sort.

function pancake_sort($array){
	$count = count($array);
	$powercount = $count - 1;
	$i = 0;
	while($i < $powercount){
		$n = 0;
		$largest = 0;
		while($n < $count){
			if($array[$largest]<$array[$n]){
				$largest = $n;
			}
			++$n;
		}
		$num = $largest/2;
		$j = 0;
		while($j < $num){
			$z = $array[$largest-$j];
			$array[$largest-$j] = $array[$j];
			$array[$j] = $z;
			++$j;
 
		}
		$num = --$count/2;
		$j = 0;
		while($j<$num){
			$z = $array[$count-$j];
			$array[$count-$j] = $array[$j];
			$array[$j] = $z;
			++$j;
		}
		++$i;
	}
	return $array;
}
Tags:

PHP implementation of Bozo sort

Tue, 01/16/2007 - 22:48 | by Mgccl

Bozo Sort is more efficient than than bogosort(in theory). It does sorting by randomly chose 2 items and compare them, then switch them if needed. Until everything is sorted.

function bozo_sort($array){
	$sorted = $array;
	sort($sorted);
	while($sorted !== $array){
		$i = array_rand($array);
		$j = array_rand($array);
		if($i < $j){
			if($array[$i] > $array[$j]){
				$z = $array[$j];
				$array[$j] = $array[$i];
				$array[$i] = $z;
			}
		}else{
			if($array[$j] > $array[$i]){
				$z = $array[$i];
				$array[$i] = $array[$j];
				$array[$j] = $z;
			}
		}
	}
	return $array;
}
Tags:

PHP implementation of Bogosort

Tue, 01/16/2007 - 21:41 | by Mgccl

Bogosort, very inefficient sorting system, now it's in PHP, even more inefficient than ever.

function bogosort($array){
	$sorted = $array;
	sort($sorted);
	while($sorted !== $array){
		shuffle($array);
	}
        return $array;
}
Tags:

PHP implementation of Dropsort

Sun, 01/14/2007 - 05:22 | by Mgccl

PHP implementation of Dropsort, a lossy sort algorithm that will drop anything that is smaller than the previous item.

function dropsort($array){
	$i = 0;
	while($array[$i]){
		if($array[$i] <= $array[$i+1]||!isset($array[$i+1])){
			++$i;
		}else{
			array_splice($array, $i+1, 1);
		}
	}
	return $array;
}

Editor Comment:

After making the Intelligent Design Sort work in PHP, this is another esoteric algorithm I implant in PHP. I guess I will make all the esoteric algorithms featured in DM's Esoteric Programming Languages work in PHP

Tags:
Honey Pot that kill bots