Упражнения с массивами PHP: Бисерная сортировка (Bead sort) массива положительных целых чисел

Бисерная сортировка (Bead sort) массива положительных целых чисел

Напишите программу PHP для сортировки массива положительных целых чисел с помощью алгоритма Bead-Sort.

Входной массив:

Ожидаемый результат:

<?php
function columns($uarr) {
$n=$uarr;
if (count($n) == 0)
 return array();
else if (count($n) == 1)
 return array_chunk($n[0], 1);
array_unshift($uarr, NULL);
 $transpose = call_user_func_array('array_map', $uarr);
return array_map('array_filter', $transpose);
}
function bead_sort($uarr) {
foreach ($uarr as $e)
 $poles []= array_fill(0, $e, 1);
return array_map('count', columns(columns($poles)));
}
echo 'Исходный массив: '.'<br>';
print_r(array(5,3,1,3,8,7,4,1,1,3));
echo 'После бисерной сортировки: '.'<br>';
print_r(bead_sort(array(5,3,1,3,8,7,4,1,1,3)));
?>

Сортировку презентовали в 2002 году три математика из Университета Окленда, что в Новой Зеландии: Джошуа Дж. Аруланандам (Joshua J. Arulanandham), Кристиан С. Калуд (Cristian S. Calude) и Майкл Дж. Динин (Michael J. Dinneen).

Бисерную сортировку (Bead sort) шариков можно сравнить с тем, как шарики скользят по параллельным полюсам, например, на счетах.

Однако на каждом полюсе может быть разное количество бусинок. Первоначально может быть полезно представить бусинки, подвешенные на вертикальных столбах.

На шаге 1 такое расположение отображается с использованием n = 5 рядов бусинок на m = 4 вертикальных полюсах. Цифры справа от каждой строки указывают номер, который представляет данная строка; строки 1 и 2 представляют положительное целое число 3 (потому что каждая из них содержит три бусинки), а верхняя строка представляет положительное целое число 2 (поскольку она содержит только две бусинки).

Если мы позволим бусинам упасть, строки теперь представляют те же целые числа в отсортированном порядке. Строка 1 содержит наибольшее число в наборе, а строка n - наименьшее. Если было выполнено вышеупомянутое соглашение о рядах, содержащих серию бусинок на полюсах 1 .. k и оставляющих полюса k +1 .. m пустыми, то это будет продолжаться и здесь.

Действие, позволяющее бусинам «падать» в нашем физическом примере, позволило большим значениям из верхних рядов распространиться на нижние ряды. Если значение, представленное строкой a, меньше, чем значение, содержащееся в строке a + 1, некоторые из бусинок из строки a + 1 попадут в строку a. Это обязательно произойдет, так как ряд a не содержит бусинок в этих положениях, чтобы предотвратить падение бусинок ряда a + 1.