Comments 21
а теперь протестируйте еще вырожденные случаи:
массив, в котором уже всё по возрастанию
массив, в котором всё по убыванию
упорядоченный массив, в котором сделали 5% случайных перестановок
результаты должны удивить.
массив, в котором уже всё по возрастанию
массив, в котором всё по убыванию
упорядоченный массив, в котором сделали 5% случайных перестановок
результаты должны удивить.
+14
Так алгоритмы стандартны, O-большое у всех известно
+2
Спасибо и на этом )))
Сами алгоритмы уже являются хрестоматийными, ни для кого не секрет их временные сложности. Но интересно кто кого обгонит практике в абсолютном времени. Графики достаточно интересные, из которых можно сделать несколько занятных выводов. При этом, конечно, не стоит забывать что это применительно к PHP, на других языках картина была бы несколько иной.
1)Гномья сортировка, оказалась чуть медленнее чем вставками. Это очень похожие алгоритмы, мне всё было интересно кто из них быстрее.
Гном и вставки «заточены» под почти отсортированные массивы, было бы интересно если бы Вы протестировали на почти упорядоченных данных. Есть мнение, что в этом случае они обгонят даже быструю сортировку.
2)Неожиданно, что чётно-нечётная сортировка оказалась медленее, чем простой пузырёк. Чёт-нечет — это вроде как модифицированый пузырёк, ан вон оно как на самом деле.
3)Пирамидальная сортировка оказалась чуть быстрее чем сортировка слиянием. Тоже прикольно, обычно в тестах наоборот.
4)Ну и стоит обратить внимание на самую недооценённую сортировку — расчёской. По скорости уступает разве что легендарной быстрой сортировке, но при этом не все знают, что такой алгоритм вообще есть. А между тем «расчёска» — это всего-навсего «пузырёк» с уменьшающимся шагом.
Сами алгоритмы уже являются хрестоматийными, ни для кого не секрет их временные сложности. Но интересно кто кого обгонит практике в абсолютном времени. Графики достаточно интересные, из которых можно сделать несколько занятных выводов. При этом, конечно, не стоит забывать что это применительно к PHP, на других языках картина была бы несколько иной.
1)Гномья сортировка, оказалась чуть медленнее чем вставками. Это очень похожие алгоритмы, мне всё было интересно кто из них быстрее.
Гном и вставки «заточены» под почти отсортированные массивы, было бы интересно если бы Вы протестировали на почти упорядоченных данных. Есть мнение, что в этом случае они обгонят даже быструю сортировку.
2)Неожиданно, что чётно-нечётная сортировка оказалась медленее, чем простой пузырёк. Чёт-нечет — это вроде как модифицированый пузырёк, ан вон оно как на самом деле.
3)Пирамидальная сортировка оказалась чуть быстрее чем сортировка слиянием. Тоже прикольно, обычно в тестах наоборот.
4)Ну и стоит обратить внимание на самую недооценённую сортировку — расчёской. По скорости уступает разве что легендарной быстрой сортировке, но при этом не все знают, что такой алгоритм вообще есть. А между тем «расчёска» — это всего-навсего «пузырёк» с уменьшающимся шагом.
0
Про сортировку слиянием действительно очень странно. Теоретически, она самая быстрая. Число сравнений у неё процентов на 10 меньше, чем у qsort, обменов (которые в 3-4 раза дороже простого копирования) нет вообще, и лишних копирований тоже нет (если правильно написать).
0
Может, влияют какие-то особенности интерпретируемых языков. Слияние наиболее прожорливо на дополнительную память.
Не берусь утверждать, насколько алгоритмы реализованы «правильно», выглядят вполне классически и стандартно.
Не берусь утверждать, насколько алгоритмы реализованы «правильно», выглядят вполне классически и стандартно.
QuickSort
function quickSort(&$a, $l = 0, $r = 0) {
if($r == 0) $r = count($a)-1;
$i = $l;
$j = $r;
$x = $a[($l + $r) / 2];
do {
while ($a[$i] < $x) $i++;
while ($a[$j] > $x) $j--;
if ($i <= $j) {
if ($a[$i] > $a[$j])
list($a[$i], $a[$j]) = array($a[$j], $a[$i]);
$i++;
$j--;
}
} while ($i <= $j);
$function = __FUNCTION__;
if ($i < $r) $function($a, $i, $r);
if ($j > $l) $function($a, $l, $j);
}
MergeSort
function mergeSort(&$a, $first = 0, $last = null) {
if (is_null($last)) $last = count($a) - 1;
$function = __FUNCTION__;
if ($first < $last) {
$function($a, $first, floor(($first + $last) / 2));
$function($a, floor(($first + $last) / 2) + 1, $last);
$tmp = array();
$middle = floor(($first + $last) / 2);
$start = $first;
$final = $middle + 1;
for ($i = $first; $i <= $last; $i++) {
if (($start <= $middle) && (($final > $last) || ($a[$start] < $a[$final]))) {
$tmp[$i] = $a[$start];
$start++;
} else {
$tmp[$i] = $a[$final];
$final++;
}
}
for ($i = $first; $i <= $last; $i++) {
$a[$i] = $tmp[$i];
}
}
}
HeapSort
function heapSort(&$a) {
$n = count($a);
heapMake($a);
while ($n > 0) {
list($a[0], $a[$n - 1]) = array($a[$n - 1], $a[0]);
$n--;
heapify($a, 0, $n);
}
}
function heapMake(&$a) {
$n = count($a);
for ($i = ($n - 1); $i >= 0; $i--) {
heapify($a, $i, $n);
}
}
function heapify(&$a, $pos, $n) {
while (2 * $pos + 1 < $n) {
$t = 2 * $pos +1;
if (2 * $pos + 2 < $n && $a[2 * $pos + 2] >= $a[$t]) {
$t = 2 * $pos + 2;
}
if ($a[$pos] < $a[$t]) {
list($a[$pos], $a[$t]) = array($a[$t], $a[$pos]);
$pos = $t;
}
else break;
}
}
0
Не знаю особенностей этого языка, но не приводит ли строчка
в MergeSort к созданию нового динамического массива при каждом вызове функции? В С-образных языках такое приводило бы к замедлению в несколько раз.
$tmp = array();
в MergeSort к созданию нового динамического массива при каждом вызове функции? В С-образных языках такое приводило бы к замедлению в несколько раз.
0
Так и есть.
Причём, конкретно в PHP массивы с одной стороны — исключительно гибкие инструменты, но, как расплата за многие возможности — далеко не самое оптимизированное звено в программе. Вот про массивы в PHP хорошая хабрастатья.
Причём, конкретно в PHP массивы с одной стороны — исключительно гибкие инструменты, но, как расплата за многие возможности — далеко не самое оптимизированное звено в программе. Вот про массивы в PHP хорошая хабрастатья.
0
Только сегодня наткнулся на визуализацию алгоритмов сортировки. [в FF лучше не открывать — падает браузер]
+1
Извините, но графики в статье просто ужасны, очень сложно понять где что.
Но за статью спасибо.
Но за статью спасибо.
+4
Как я понял, автор взял те сортировки, которые есть в русской Википедии. А почему нет поразрядной сортировки (radix sort)? При чём интересно было бы сравнить между собой обе разновидности — MSD и LSD.
0
Для целочисленных массивов хорошо реализованная LSD в общем случае быстрее, чем MSD (не смотря на то, что теоретически должно быть наоборот). При этом для 32-битных чисел можно сделать LSD вариант, который обгоняет quiсksort уже при 60-70 элементах (я слышал и про более ранний обгон (30-40), но никогда не видел подобный код — там видимо хорошо проработанные SSE оптимизации используются).
И простите за оффтоп, но я просмотрел Ваш сайт про сортировки и там как раз в разделе про radix sort ошибка:
«Кроме того, MSD, в отличие от LSD, является устойчивым алгоритмом.» LSD безусловно является устойчивым алгоритмом, а вот как раз с MSD все не так просто. Наиболее быстрая in-place реализация не является устойчивой, а вот сделать такую же быструю реализацию устойчивой MSD сортировки с дополнительной памятью не получается на сколько я знаю.
И простите за оффтоп, но я просмотрел Ваш сайт про сортировки и там как раз в разделе про radix sort ошибка:
«Кроме того, MSD, в отличие от LSD, является устойчивым алгоритмом.» LSD безусловно является устойчивым алгоритмом, а вот как раз с MSD все не так просто. Наиболее быстрая in-place реализация не является устойчивой, а вот сделать такую же быструю реализацию устойчивой MSD сортировки с дополнительной памятью не получается на сколько я знаю.
+1
Я конечно могу быть неправ, но усреднять значение по 3-м замерам, вероятно, маловато.
А уж если совсем придираться, то для таких вещей нужно говорить о доверительной вероятности результатов.
А уж если совсем придираться, то для таких вещей нужно говорить о доверительной вероятности результатов.
+2
На мой взгляд графики стоило рисовать в логарифмических масштабах. Тогда бы не было такого слипания вблизи нуля.
+1
Зачем нужна еще одна не идеальная статья о сортировках?
0
Стандартная сортировка ощутимо быстрее qsort… В гугле написано, что она использует её же, но мне кажется, что по скорости больше похоже на IntroSort
0
Интроспективная сортировка работает быстрее, только если подсунули массив-убийцу (специально подобранный массив являющийся для быстрой сортировки вырожденным случаем). В этом случае IntroSort переключается с использования QuickSort на HeapSort, что может ускорить процесс даже в сотни раз. На обычных массивах, даже очень больших, скорость будет примерно одинакова (маловероятно что массив случайно окажется вырожденным случаем), потому что IntroSort просто использует оптимизированную QuickSort.
0
Sign up to leave a comment.
Бенчмарк 14 алгоритмов сортировки на массивах с разной размерностью и содержанием