Ilya Rogozhin
111 lines
4.1 KiB
PHP
111 lines
4.1 KiB
PHP
<?php
|
|
|
|
namespace App\Console\Commands;
|
|
|
|
use Illuminate\Console\Attributes\Description;
|
|
use Illuminate\Console\Attributes\Signature;
|
|
use Illuminate\Console\Command;
|
|
|
|
#[Signature('app:test-fhr-sort')]
|
|
#[Description('Написать сортировку для массива числовых данных от 200 тысяч элементов')]
|
|
class TestFHRSort extends Command
|
|
{
|
|
/**
|
|
* Execute the console command.
|
|
*/
|
|
public function handle()
|
|
{
|
|
$this->info('Starting the sort test...');
|
|
|
|
$count = 200000;
|
|
$this->comment("Generating an array of $count random numbers...");
|
|
|
|
$array = [];
|
|
for ($i = 0; $i < $count; $i++) {
|
|
$array[] = rand(-200000, $count);
|
|
}
|
|
|
|
$memoryBefore = memory_get_usage();
|
|
$timeBefore = microtime(true);
|
|
|
|
$this->comment('Before sorting:');
|
|
$this->comment('Memory usage: ' . round($memoryBefore / 1024 / 1024, 2) . ' MB');
|
|
|
|
$this->info('Sorting the array using manual Quicksort implementation...');
|
|
|
|
$this->quickSort($array, 0, count($array) - 1);
|
|
|
|
$timeAfter = microtime(true);
|
|
$memoryAfter = memory_get_usage();
|
|
|
|
$this->comment('After sorting:');
|
|
$this->comment('Memory usage: ' . round($memoryAfter / 1024 / 1024, 2) . ' MB');
|
|
$this->comment('Memory increase: ' . round(($memoryAfter - $memoryBefore) / 1024, 2) . ' KB');
|
|
$this->comment('Time taken: ' . round($timeAfter - $timeBefore, 4) . ' seconds');
|
|
|
|
$this->line('');
|
|
$this->info('First 12 elements:');
|
|
$this->line(implode(', ', array_slice($array, 0, 12)));
|
|
|
|
$this->info('Last 12 elements:');
|
|
$this->line(implode(', ', array_slice($array, -12)));
|
|
|
|
$this->info('Sort test finished.');
|
|
}
|
|
|
|
/**
|
|
* Реализация алгоритма Быстрой сортировки (Quicksort) "на месте".
|
|
* @param array $arr Сортируемый массив (передается по ссылке).
|
|
* @param int $low Индекс начала подмассива.
|
|
* @param int $high Индекс конца подмассива.
|
|
*/
|
|
private function quickSort(array &$arr, int $low, int $high): void
|
|
{
|
|
if ($low < $high) {
|
|
// pi - это индекс опорного элемента, arr[pi] теперь на своем месте.
|
|
$pi = $this->partition($arr, $low, $high);
|
|
|
|
// Рекурсивно сортируем элементы до и после опорного.
|
|
$this->quickSort($arr, $low, $pi - 1);
|
|
$this->quickSort($arr, $pi + 1, $high);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Вспомогательная функция для quickSort.
|
|
* Разделяет массив на две части относительно опорного элемента.
|
|
* @param array $arr
|
|
* @param int $low
|
|
* @param int $high
|
|
* @return int Индекс, на котором теперь стоит опорный элемент.
|
|
*/
|
|
private function partition(array &$arr, int $low, int $high): int
|
|
{
|
|
// В качестве опорного элемента (pivot) берем последний элемент.
|
|
$pivot = $arr[$high];
|
|
|
|
// i - индекс меньшего элемента.
|
|
$i = ($low - 1);
|
|
|
|
for ($j = $low; $j <= $high - 1; $j++) {
|
|
// Если текущий элемент меньше или равен опорному.
|
|
if ($arr[$j] <= $pivot) {
|
|
$i++; // Увеличиваем индекс меньшего элемента.
|
|
|
|
// Меняем местами arr[i] и arr[j].
|
|
$temp = $arr[$i];
|
|
$arr[$i] = $arr[$j];
|
|
$arr[$j] = $temp;
|
|
}
|
|
}
|
|
|
|
// Ставим опорный элемент на его правильную позицию,
|
|
// меняя местами arr[i+1] и arr[high] (опорный элемент).
|
|
$temp = $arr[$i + 1];
|
|
$arr[$i + 1] = $arr[$high];
|
|
$arr[$high] = $temp;
|
|
|
|
return ($i + 1);
|
|
}
|
|
}
|