PHP - ソートの比較
PHPってインタプリタだけどソートのアルゴリズムを比較してみる。PHPでやるのはお勧めしない!
実行結果(レンタルサーバでは負荷をかけられないので自宅の Mac OS X で実行)
Bubble Sort: 0.0016670227050781 s Quick Sort: 0.00027203559875488 s
ソースコード
<?php
$aryData1 = array(
5, 12, 4, 2, 18, 8, 2, 7, 31, 72,
8, 33, 0, 73, 38, 66, 88, 10, 5, 56,
4, 22, 89, 51, 72, 98, 19, 19, 53, 26,
0, 79, 44, 70, 15, 17, 28, 9, 71, 15,
2, 23, 61, 92, 68, 23, 40, 3, 87, 7,
7, 59, 57, 85, 20, 46, 60, 21, 92, 8,
9, 93, 64, 30, 5, 0, 5, 80, 12, 46,
6, 84, 11, 6, 47, 39, 99, 37, 29, 96,
3, 14, 9, 66, 58, 69, 13, 59, 18, 13,
1, 42, 26, 76, 55, 77, 20, 35, 23, 64,
);
$aryData2 = array(
5, 12, 4, 2, 18, 8, 2, 7, 31, 72,
8, 33, 0, 73, 38, 66, 88, 10, 5, 56,
4, 22, 89, 51, 72, 98, 19, 19, 53, 26,
0, 79, 44, 70, 15, 17, 28, 9, 71, 15,
2, 23, 61, 92, 68, 23, 40, 3, 87, 7,
7, 59, 57, 85, 20, 46, 60, 21, 92, 8,
9, 93, 64, 30, 5, 0, 5, 80, 12, 46,
6, 84, 11, 6, 47, 39, 99, 37, 29, 96,
3, 14, 9, 66, 58, 69, 13, 59, 18, 13,
1, 42, 26, 76, 55, 77, 20, 35, 23, 64,
);
$iStart = microtime(true);
bsort($aryData1);
$iEnd = microtime(true);
fputs(STDERR, "Bubble Sort: ".($iEnd - $iStart)." s\n");
$iStart = microtime(true);
qsort($aryData2, 0, count($aryData2)-1);
$iEnd = microtime(true);
fputs(STDERR, "Quick Sort: ".($iEnd - $iStart)." s\n");
//print_r($aryData1);
//print_r($aryData2);
/**
* Bubble Sort
*/
function bsort(&$aryData)
{
$iCount = count($aryData) - 1;
for ($i=0; $i<$iCount; $i++) {
for ($j=0; $j<$iCount-$i; $j++) {
if ($aryData[$j] > $aryData[$j+1]) {
swap($aryData[$j], $aryData[$j+1]);
}
}
}
}
/**
* Quick Sort
*/
function qsort(&$aryData, $iLeft, $iRight) {
$pivot = $aryData[$iLeft];
$i = $iLeft;
$j = $iRight;
while(1) {
while($aryData[$i] < $pivot) {
$i++;
}
while($pivot < $aryData[$j]) {
$j--;
}
if ($i >= $j) {
break;
}
swap($aryData[$i], $aryData[$j]);
$i++;
$j--;
}
if ($iLeft < ($i - 1)) {
qsort($aryData, $iLeft, $i-1);
}
if (($j + 1) < $iRight) {
qsort($aryData, $j+1, $iRight);
}
}
function swap(&$a, &$b) {
$tmp = $a;
$a = $b;
$b = $tmp;
}
?>