Sort

Much better than quicksort!

Posted June 10th, 2007 by Mgccl
in

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.

PHP implementation of Pancake sort

Posted January 19th, 2007 by Mgccl
in

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

PHP implementation of Bozo sort

Posted January 16th, 2007 by Mgccl
in

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

PHP implementation of Bogosort

Posted January 16th, 2007 by Mgccl
in

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

PHP implementation of Dropsort

Posted January 14th, 2007 by Mgccl
in

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

12next ›last »
Syndicate content
Honey Pot that kill bots