Как работает алгоритм сортировки usort ()?

1. Как работает компаратор?

Я не уверен, что это было частью вопроса, но чтобы понять, как работает компаратор:
У вас есть заказ, указанный в упорядоченном списке $order и специальный обратный вызов компаратора list_cmp который (должен) вернуть более влажный аргумент

• $a меньше чем $b (return -1 или значение < 0)
• $a лучше чем $b (return 1 или значение > 0)
• $a равный $b (return 0)

list_cmp делает это, глядя на его стол заказов и скорее проверка, если

• $a имеет меньший (или равный) порядок, в этом случае цикл выходит рано с return 0 или если
• $b имеет меньший порядок, в этом случае цикл выходит рано с return 1,

Помните, что это неправильно в соответствии с документацией PHP, в которой говорится, что в качестве возвращаемых значений требуется положительное / отрицательное / 0. Это верно только в том случае, если вы знаете, что внутреннее устройство проверяет только comparator($a,$b) > 0Это означает, что он проверяет только $b меньше чем и не равно $aделая это сравнение order of $a <= order of $b, Это может легко сломаться, если код начинает проверять $a быть меньше и не равно $b,

2. Как работает быстрая сортировка сортировочная работа?

Для начала я предполагаю, что вы используете PHP 7 или выше. В этом случае вы попадаете в особый случай с массивами размером 6-15 элементов. Похоже, что PHP 7+ не использует быструю сортировку для коротких списков, вместо этого он использует вариант сортировки вставкой (который, скорее всего, быстрее из-за аппаратных средств, таких как кэширование / локальность кода). Вы можете проверить исходный код сортировки f.e. на Github PHP Mirror (как пример: PHP 7.0 Zend / Zend_sort.c Строка 177-198).

Код работает в 3 этапа:

1. Comparision: сравнить соседние элементы array[j] а также array[j+1], если array[j] <= array[j+1] двигаться дальше, иначе перейти к 2.
2. найти точку вставки: сейчас если array[j] > array[j+1], отсканируйте назад, чтобы найти точку, где array[x] < array[j+1] <= array[x+1] за x < j (очевидно, только до x бьет по началу)
3. вставить: элементы сдвига x+1 ... j один такой, что становится x+2 ... j+1 и вставьте бывший элемент в положение x+1

Если вы примените этот код к парам (2-1, 2-3, 1-3, 2-4, 3-4, 2-2, 2-1, 2-1, 4-1, 3-1, 1 -1, 2-2) становится понятно, что делает код.

-- [2,1],3,4,2,1,2 -> 1./2./3. compare [2,1], find and insert 1 before 2
-- 1,[2,3],4,2,1,2 -> 1./2. compare [2,3], find insert point for 3 (since order of 3 < order of 2)
-- [1,3],2,4,2,1,2 -> 3. compare [1,3], found insert point for 3 before 2
-- 1,3,[2,4],2,1,2 -> 1./2. compare [2,4], find insert point for 4 (since order of 4 < order of 2)
-- 1,[3,4],2,2,1,2 -> 3. compare [3,4], found insert point for 4 before 2
-- 1,3,4,[2,2],1,2 -> 1. compare [2,2], skip
-- 1,3,4,2,[2,1],2 -> 1./2. compare [2,1], find insert point for 1
-- 1,3,4,[2,1],2,2 -> 2. compare [2,1], find insert point for 1
-- 1,3,[4,1],2,2,2 -> 2. compare [4,1], find insert point for 1
-- 1,[3,1],4,2,2,2 -> 2. compare [3,1], find insert point for 1
-- [1,1],3,4,2,2,2 -> 3. compare [1,1], fond insert point for 1 before 3
-- 1,1,3,4,2,[2,2] -> 1. compare [2,2], skip
-- sorted: 1,1,3,4,2,2,2

PS:
Здесь вы уже видите, что довольно сложно вывести работу даже простого алгоритма сортировки (22 строки кода) по шаблонам сравнения. Реализация быстрой сортировки в PHP 7 примерно в 10 раз больше в строках кода и имеет несколько причудливых оптимизаций (помимо обычного безумия из-за выбора и поворотов сводки).

В большинстве случаев лучше игнорировать подробности реализации и сводить их только к тому, что нужно. Типичные вопросы для алгоритма сортировки были бы, если он стабилен / нестабилен и работает в O(log n) с O(n) Потребление памяти. Существуют более простые способы изучения основных алгоритмов этих оптимизированных реализаций, таких как Quicksort Dance или любую другую визуализацию или старую (электронную) книгу или веб-страницу с примерами.

— отредактированный

Добавлена ​​(плохая, неоптимизированная, небезопасная) реализация php для вставки сортировки для другой визуализации того, как она работает:

<?php

function my_usort($A, $comparator) {
// Start .. End Positions
$current_pos = 0;
$last_pos = count($A)-1;
// Outer Loop: each step checks that A[0] up to A[current_pos] is sorted.
// When the algorithm finishes we know that A[0] ... A[last_pos] is sorted
while($current_pos < $last_pos) {
echo "Sorted Subarray from \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
echo "\$A looks like this now: " . json_encode($A) .
", comparing [" . $A[$current_pos] . "," . $A[$current_pos +1] . "] (verify step)<br>\n";
// "Verification Step"// At this point A[0] ... A[current_pos] is sorted.
// Check A[current_pos] <= A[current_pos +1]
if($comparator($A[$current_pos], $A[$current_pos +1]) > 0) {
// nope, A[current_pos] > A[current_pos +1] (list_cmp/comparator returns value > 0)
// "Insertion Step" start, find the correct position for A[current_pos+1] in the already
// sorted list A[0] ... A[current_pos]
$insert_point = $current_pos;
// Swap the missmatching Neighbor pair
echo "swapping: \$A[" . $insert_point . "] and \$A[" . ($insert_point+1) . "]<br>\n";
$tmp = $A[$insert_point +1];
$A[$insert_point +1] = $A[$insert_point];
$A[$insert_point] = $tmp;
$sorted_up_to_current_pos = false;
// Inner Loop: find correct insertion point
while($insert_point > 0 && !$sorted_up_to_current_pos) {
echo "\$A looks like this now: " . json_encode($A) .
", comparing [" . $A[$insert_point-1] . "," . $A[$insert_point] . "] (insertion step)<br>\n";
// "Insertion Step", Swap the missmatching Neighbor pairs until A[0] ... A[current_pos] is sorted again
if($comparator($A[$insert_point-1], $A[$insert_point]) > 0) {
// Swap the missmatching Neighbor pair
echo "swapping: \$A[" . ($insert_point-1) . "] and \$A[" . $insert_point . "]<br>\n";
$tmp = $A[$insert_point];
$A[$insert_point] = $A[$insert_point-1];
$A[$insert_point-1] = $tmp;
// goto new pair
$insert_point = $insert_point -1;
} else {
// found correct spot, done
$sorted_up_to_current_pos = true;
}
}
$A[$insert_point] = $tmp;
echo "\$A looks like this now: " . json_encode($A) . ", insertion done<br>\n";
}
$current_pos = $current_pos + 1;
}
echo "Sorted Array \$A is " . json_encode(array_slice($A, 0, $current_pos+1)) . "<br>\n";
}

function list_cmp($a, $b) {
global $order;
//echo "\$a=$a, \$b=$b </br>\n";

foreach ($order as $key => $value) {
//echo "\$value=$value </br>\n";
if ($a == $value) {
echo "\$a=\$value, returing 0. </br>\n";
return 0;
}
if ($b == $value) {
echo "\$b=\$value, returing 1. </br>\n";
return 1;
}
}
}

$order[0] = 1;
$order[1] = 3;
$order[2] = 4;
$order[3] = 2;

$array[0] = 2;
$array[1] = 1;
$array[2] = 3;
$array[3] = 4;
$array[4] = 2;
$array[5] = 1;
$array[6] = 2;

my_usort($array, "list_cmp");

Вывод завершен, теперь отсортированный массив, позиции:

Sorted Subarray from $A is [2]
$A looks like this now: [2,1,3,4,2,1,2], comparing [2,1] (verify step)
$b=$value, returing 1.
swapping: $A[0] and $A[1]
$A looks like this now: [1,2,3,4,2,1,2], insertion done
Sorted Subarray from $A is [1,2]
$A looks like this now: [1,2,3,4,2,1,2], comparing [2,3] (verify step)
$b=$value, returing 1.
swapping: $A[1] and $A[2]
$A looks like this now: [1,3,2,4,2,1,2], comparing [1,3] (insertion step)
$a=$value, returing 0.
$A looks like this now: [1,3,2,4,2,1,2], insertion done
Sorted Subarray from $A is [1,3,2]
$A looks like this now: [1,3,2,4,2,1,2], comparing [2,4] (verify step)
$b=$value, returing 1.
swapping: $A[2] and $A[3]
$A looks like this now: [1,3,4,2,2,1,2], comparing [3,4] (insertion step)
$a=$value, returing 0.
$A looks like this now: [1,3,4,2,2,1,2], insertion done
Sorted Subarray from $A is [1,3,4,2]
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,2] (verify step)
$a=$value, returing 0.
Sorted Subarray from $A is [1,3,4,2,2]
$A looks like this now: [1,3,4,2,2,1,2], comparing [2,1] (verify step)
$b=$value, returing 1.
swapping: $A[4] and $A[5]
$A looks like this now: [1,3,4,2,1,2,2], comparing [2,1] (insertion step)
$b=$value, returing 1.
swapping: $A[3] and $A[4]
$A looks like this now: [1,3,4,1,2,2,2], comparing [4,1] (insertion step)
$b=$value, returing 1.
swapping: $A[2] and $A[3]
$A looks like this now: [1,3,1,4,2,2,2], comparing [3,1] (insertion step)
$b=$value, returing 1.
swapping: $A[1] and $A[2]
$A looks like this now: [1,1,3,4,2,2,2], comparing [1,1] (insertion step)
$a=$value, returing 0.
$A looks like this now: [1,1,3,4,2,2,2], insertion done
Sorted Subarray from $A is [1,1,3,4,2,2]
$A looks like this now: [1,1,3,4,2,2,2], comparing [2,2] (verify step)
$a=$value, returing 0.
Sorted Array $A is [1,1,3,4,2,2,2]