PHP
アルゴリズム
データ構造
ソート

PHPでマージソートしてみる

More than 1 year has passed since last update.


はじめに

Javaで書かれたマージソートをPHPで書き換えてみたら思ったより時間がかかったのでメモ。

できたコードはこんな感じ

class MergeSort 

{
public $array;

function __construct($ary)
{
$this->array = $ary;
}
function run()
{
$this->mergeSort(0, count($this->array));
}

function mergeSort($low, $high)
{
if ($high - $low <= 1) return;
$middle = (int)($low + ($high - $low) / 2);
$this->mergeSort($low, $middle);
$this->mergeSort($middle, $high);
$this->merge($low, $middle, $high);
echo "<pre>";
print_r($this->array);
echo "</pre>";
}

function merge($low, $middle, $high)
{
$helper = array();
$helperLeft = $low;
$helperRight = $middle;

while ($helperLeft < $middle && $helperRight < $high) {
if ($this->array[$helperLeft] <= $this->array[$helperRight]) {
$result[] = $this->array[$helperLeft];
$helperLeft++;
} else {
$result[] = $this->array[$helperRight];
$helperRight++;
}
}
while ($helperLeft < $middle) {
$result[] = $this->array[$helperLeft];
$helperLeft++;
}
while ($helperRight < $high) {
$result[] = $this->array[$helperRight];
$helperRight++;
}
$this->arrayCopy($result, $low, $high);
}

function arrayCopy($resource, $start, $end)
{
$resIndex = 0;
for ($i = $start; $i < $end; $i++) {
$this->array[$i] = $resource[$resIndex];
$resIndex++;
}
}
}

$ary = range(1, 10, 1);
shuffle($ary);

$mergeSort = new MergeSort($ary);
$mergeSort->run();


つまずいたポイント

1 PHPでは引数に配列を渡すと参照渡しではなくとしてコピーされる

2. 参照渡しはパフォーマンス的にも宜しくない -> 配列を操作するアルゴリズムを関数にしてはいけない?

3. 整数同士の割り算でも実数値になる


解決1

配列が参照渡しされるように引数の前に&をつけて見たものの下の記事を拝見するといいやり方ではないよう、、

たいてい配列は参照渡しだろーと思っていたので思わぬところでつまずいた汗 PHPの変数は最初からすべてポインタであるため参照渡しを明示してやる必要はない。よって関数に配列が渡されたときに値がまるまるコピーされるわけではないので、&をつける必要がない。むしろパフォーマンスが悪くなる。


解決2

参照渡しをしないで配列を操作するアルゴリズムをどう書けばいいのか悩んだ結果、同じ方のとても参考になる記事を見つけた。配列の中身を変更するのであれば関数ではなく、クラス化して状態をもたせるのがいいみたい。


解決3

CやJavaでは整数同士の割り算は整数値になるが、PHPでは実数値になるためキャストする必要がある。

PHP7のintdiv関数でもいけると思ったが、Fatal error: Allowed memory size of ~とエラーがでて動かなかった...