Десять алгоритмов сортировки массива на PHP

Совсем недавно я ругался, что PHP - не язык для вычислительных сервисов и экспериментов, а у самого такого добра тоже немало. Просто удобно на нём писать, паршивце.

Ниже прикреплю небольшой скрипт на классическую тему - для запуска и сравнения методов сортировки массива числовых значений. Размещать этот сервис онлайн я не буду, но вы легко можете скачать исходники и установить его себе на локальный хост или реальный хостинг.

Список применяемых методов сортировки неполон, кроме того, исключён ряд известных алгоритмов, например, сортировка подсчётом и Bead sort, "в норме" сортирующие только неотрицательные значения, или сортировка по частям, требующая дополнительных аргументов, кроме параметра-массива, или заведомо тупейшая "обезьянья".

Основной файл index.php выводит форму и запускает весь процесс, вот скриншот:

методы сортировки на PHP, окно приложения (фрагмент)

Время выполнения скрипта предполагается неограниченным, поэтому ограничена размерность массива, всё это легко поменять в исходниках.

Модуль functions.php содержит функции для методов сортировки и пару простых сервисных методов - генерация массива случайных значений размерности $n из диапазона [$min;$max] и вывод массива в абзац текста, только их и приведу:

function generateArray ($n,$min,$max) {
 $arr = Array ();
 for ($i = 0; $i < $n; $i++) $arr[] = mt_rand ($min, $max);
 return $arr;
}

function print_array ($hdr,$a) {
 if (!is_array($a)) return '<p>Object with header '.$hdr.' is not Array!</p>';
 $n = count ($a); 
 $s = '<p>'.$hdr.' ';
 for ($i = 0; $i < $n; $i++) $s .= $a[$i].($i<$n-1?', ':'');
 return $s.'</p>'."\n";
}

Класс для снятия меток времени timer.php заметно упрощён по сравнению с этим:

<?php
class timer {
 private $t;

 public function __construct () {
  $this->t = 0;
 }

 public function start() {
  $this->t = microtime (true);
  return $this->t;
 }
 
 public function finish() {
  return microtime (true) - $this->t;
 }
}
?>

Всем файлам нужен PHP 5.0 и выше, кодировка файлов из архива - Юникод (utf-8).

Вот результаты моего прогона скрипта на локальном хосте, разумеется, ваши цифры могут отличаться.

Отсортировано алгоритмом: Пузырьком, время = 0.640625 с.

Отсортировано алгоритмом: Перемешиванием, время = 0.734375 с.

Отсортировано алгоритмом: Расчёской, время = 0.015625 с.

Отсортировано алгоритмом: Гномья, время = 0.53125 с.

Отсортировано алгоритмом: Вставками, время = 0.3125 с.

Отсортировано алгоритмом: Слиянием, время = 0.109375 с.

Отсортировано алгоритмом: Терпеливая, время = 0.328125 с.

Отсортировано алгоритмом: Быстрая, время = 0.015625 с.

Отсортировано алгоритмом: Выбором, время = 0.453125 с.

Отсортировано алгоритмом: Шелла, время = 0.015625 с.

Даже из этого элементарного теста на быстродействие видно, какие алгоритмы сортировки лучше. Выполнялся он всего-то на 999 элементах, для более достоверных тестов следует увеличить размерности в скрипте и пользоваться компом, которого не жалко :)

 Скачать скрипт в архиве .zip, папка для размещения уже создана в архиве (4 Кб)

24.02.2018, 13:49 [6764 просмотра]