← All source

PHP — quicksort.php

wsl.exe -d Ubuntu -- bash -c "cd '/mnt/c/Users/granite/Documents/DSU/Algorithms 482/3/HW3/php' && php quicksort.php"

<?php
/**
 * HW3 - Language Comparison: Randomized Quicksort in PHP
 *
 * Implements CLRS Ch. 5 RANDOMIZED-QUICKSORT / RANDOMIZED-PARTITION:
 * in-place quicksort where, at every partition step, the pivot is chosen
 * uniformly at random from the current subarray range and swapped into the
 * last position before running a standard Lomuto partition.
 *
 * No external code used - original implementation based on CLRS pseudocode.
 * No sort()/usort() built-ins are used for the actual sorting logic.
 */

declare(strict_types=1);

/**
 * Standard Lomuto partition around a[hi] as pivot.
 * Returns the final index of the pivot element.
 *
 * @param array<int,int> $a
 */
function partition(array &$a, int $lo, int $hi): int
{
    $pivot = $a[$hi];
    $i = $lo - 1;
    for ($j = $lo; $j < $hi; $j++) {
        if ($a[$j] <= $pivot) {
            $i++;
            $tmp = $a[$i];
            $a[$i] = $a[$j];
            $a[$j] = $tmp;
        }
    }
    $tmp = $a[$i + 1];
    $a[$i + 1] = $a[$hi];
    $a[$hi] = $tmp;
    return $i + 1;
}

/**
 * RANDOMIZED-PARTITION: pick a pivot index uniformly at random from
 * [lo, hi], swap it into position hi, then run the standard partition.
 *
 * @param array<int,int> $a
 */
function randomizedPartition(array &$a, int $lo, int $hi): int
{
    $randomIndex = random_int($lo, $hi);
    $tmp = $a[$randomIndex];
    $a[$randomIndex] = $a[$hi];
    $a[$hi] = $tmp;
    return partition($a, $lo, $hi);
}

/**
 * RANDOMIZED-QUICKSORT: recursively sort a[lo..hi] in place.
 *
 * @param array<int,int> $a
 */
function randomizedQuicksort(array &$a, int $lo, int $hi): void
{
    if ($lo < $hi) {
        $p = randomizedPartition($a, $lo, $hi);
        randomizedQuicksort($a, $lo, $p - 1);
        randomizedQuicksort($a, $p + 1, $hi);
    }
}

/**
 * Generate an array of n random integers in [0, 1_000_000).
 *
 * @return array<int,int>
 */
function generateRandomArray(int $n): array
{
    $a = [];
    for ($k = 0; $k < $n; $k++) {
        $a[$k] = mt_rand(0, 999999);
    }
    return $a;
}

/**
 * Sanity check that the array is sorted ascending.
 *
 * @param array<int,int> $a
 */
function isSorted(array $a): bool
{
    $n = count($a);
    for ($k = 1; $k < $n; $k++) {
        if ($a[$k - 1] > $a[$k]) {
            return false;
        }
    }
    return true;
}

function main(): void
{
    $resultsDir = __DIR__ . '/../results';
    if (!is_dir($resultsDir)) {
        mkdir($resultsDir, 0777, true);
    }
    $csvPath = $resultsDir . '/php.csv';

    $fh = fopen($csvPath, 'w');
    if ($fh === false) {
        fwrite(STDERR, "Failed to open $csvPath for writing\n");
        exit(1);
    }
    fwrite($fh, "n,time_seconds\n");

    echo "n,time_seconds\n";

    $n = 1000;
    $iteration = 0;
    $maxIterations = 25;
    $maxN = 200_000_000;
    $timeCutoff = 4.0;

    while (true) {
        $iteration++;

        $a = generateRandomArray($n);

        $start = hrtime(true);
        randomizedQuicksort($a, 0, $n - 1);
        $end = hrtime(true);

        $elapsedSeconds = ($end - $start) / 1_000_000_000.0;

        if (!isSorted($a)) {
            fwrite(STDERR, "ERROR: array of size $n did not sort correctly!\n");
            exit(1);
        }

        $line = sprintf("%d,%.6f\n", $n, $elapsedSeconds);
        fwrite($fh, $line);
        fflush($fh);
        echo $line;

        if ($elapsedSeconds > $timeCutoff) {
            break;
        }
        if ($iteration >= $maxIterations) {
            break;
        }
        if ($n * 2 > $maxN) {
            break;
        }

        $n *= 2;
    }

    fclose($fh);
}

main();

Read PHP report