Как проверить сортировку на стабильность

Алгоритм сортировки считается стабильным (см. столбец "Stable" в таблице Вики), если при сортировке записей по определённому столбцу или полю он всегда сохраняет относительный порядок элементов с одинаковым ключом, например, для исходного массива [0; 2; 0; 1], конечно, получится [0; 0; 1; 2], но первый из двух нулей в исходном массиве останется первым и в отсортированном.

В простейшем случае чтобы проверить алгоритм сортировки на стабильность можно руководствоваться следующим алгоритмом:

• создать список объектов, которые рандомизируются на основе их критерия сортировки;
• сохраняя тот же порядок объектов, добавить последовательный идентификатор к каждому объекту. Этот идентификатор не должен быть частью критериев сортировки;
• отсортировать объекты в порядке возрастания по выбранному критерию (столбцу).

Теперь можно просмотреть отсортированный массив или список и проверить только одинаковые элементы на предмет того, расположены ли их идентификаторы в порядке возрастания. Если да, то сортировка ведёт себя как стабильная, в противном случае - нет.

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

Так как в PHP удобно обращаться с ассоциативными массивами, проделаем тестирование на нём. Мы получим массив $arr из $n случайных неотрицательных целых чисел, значения которых лежат в диапазоне [0;$m], затем преобразуем его в массив массивов вида ['k'=>ключ; 'v'=>значение], чтобы запомнить в 'k' исходные индексы элементов, а затем отсортируем полученный массив массивов стандартной функцией usort.

<?php
 $n = 50;
 $m = 10;
 $arr = array_map(function () use ($m) { return rand(0, $m); }, array_fill(0, $n, null));
 print_r($arr); //массив из $n элементов в диапазоне [0;$m]
 $a = [];
 foreach ($arr as $key=>$value) $a[] = ['k'=>$key,'v'=>$value];
 echo '<hr>'; print_r($a); //массив из массивов ['k'=>ключ; 'v'=>значение]
 usort ($a, function ($v1,$v2) { return $v1['v']-$v2['v']; } );
 echo '<hr>'; print_r($a); //массив, отсортированный по возрастанию значения 'v'
?>

результат сортировки в PHP 8.X - стабильна!

По картинке видно, что в PHP 8.X стандартные алгоритмы сортировки стабильны, например, нули, бывшие в исходном массиве на позициях 16, 33 и 43, в полученном после сортировке массиве следуют в том же порядке.

Существенно, что свойством стабильной сортировки PHP обладает только с восьмой версии, тот же код, выполненный в PHP 7.4 не сохранил на выходе позиции нулей 1, 3, 21 и 29 в исходном порядке:

результат сортировки в PHP 7.4.X - нестабильна!

12.09.2022, 18:33 [451 просмотр]