PHPでクイックソート

copy

<?php

function writequick()
{
  // csvファイルを読み込みます
  $csvfile = 'input.csv';
  if (!file_exists($csvfile)) {
    print '読み込むファイルがありません';
    return;
  }
  $file = fopen($csvfile, 'r');
  $records = [];
  // 入れ子の配列を作成します
  while (($line = fgetcsv($file, 256, ',')) !== FALSE) {
    $records[] = $line;
  }
  fclose($file);

  // ソートの実行
  quick($records, 0, count($records) - 1);

  // 書き込み用の文字列を作成します
  $output = [];
  // 入れ子の配列をカンマで繋いで一つの文字列にして配列を作成します
  foreach ($records as $line) {
    $output[] = implode(',', $line);
  }
  // 配列を改行で繋いで一つの文字列にします
  $writecsv = implode("\n", $output);

  // これをファイルに書き込みます
  $csvfile = 'output.csv';
  $file = fopen($csvfile, 'w');
  flock($file, LOCK_EX);
  fwrite($file, $writecsv);
  flock($file, LOCK_UN);
  fclose($file);
}

// 再帰関数を使ってソートを実行します
function quick(&$records, int $left, int $right)
{
  if ($left < $right) {
    $posi = getposi($records, $left, $right);
    quick($records, $left, $posi - 1);
    quick($records, $posi + 1, $right);
  }
  return;
}

// ピボットの軸を求める関数です
function getposi(&$records, int $leftposi, int $rightposi): int
{
  // 配列の中央をピボットにします
  $center = floor(($rightposi + $leftposi) / 2);
  // 右端と入れ替えます
  swap($records[$center], $records[$rightposi]);
  $i = $leftposi;
  $j = $rightposi - 1;
  // 無限ループで左右からピボットと比較してピボットの位置を求めます
  while (true) {
    // ピボットより小さいものであれば進めます
    while ($i < $rightposi && leftnext($records[$rightposi], $records[$i])) {
      $i += 1;
    }
    // ピボットより大きいならば進めます
    while ($j > $leftposi && rightnext($records[$rightposi], $records[$j])) {
      $j -= 1;
    }
    // 左右から進めた結果交差したならループを抜けます
    if ($i >= $j) {
      break;
    }
    // 交差するまでピボットより大きいものと小さいものと入れ替えループします
    swap($records[$i], $records[$j]);
  }
  // 交差した結果ピボットの位置がきまり、入れ替えます
  swap($records[$i], $records[$rightposi]);
  return $i;
}

// 入れ替えの関数です
function swap(&$a, &$b)
{
  [$a[0], $b[0]] = [$b[0], $a[0]];
  [$a[1], $b[1]] = [$b[1], $a[1]];
}

// 左からの進行条件を判定する関数です
function leftnext($pivotval, $leftval): bool
{
  $res = $pivotval[0] <=> $leftval[0];
  if ($res == 0) {
    $res = $pivotval[1] <=> $leftval[1];
  }
  return $res >= 0;
}

// 右からの進行条件を判定する関数です
function rightnext($pivotval, $rightval): bool
{
  $res = $pivotval[0] <=> $rightval[0];
  if ($res == 0) {
    $res = $pivotval[1] <=> $rightval[1];
  }
  return $res < 0;
}

xamppで実行

xampp の公開フォルダー localhost となるフォルダー htdocs に、PHPファイルとソートするファイルinput.csvファイルを置いてブラウザで開いてみます。

この例では下の画像のように quick フォルダーを作り、そこにファイルを置きました。

ブラウザのURLに次のように入力して開くと実行します。

http://localhost/quick/quicksort.php

実行の結果