Pull to refresh

Comments 21

а теперь протестируйте еще вырожденные случаи:
массив, в котором уже всё по возрастанию
массив, в котором всё по убыванию
упорядоченный массив, в котором сделали 5% случайных перестановок

результаты должны удивить.
И не плохо было бы добавить еще Timsort, который с такого рода данными вроде хорошо дружит.
Так алгоритмы стандартны, O-большое у всех известно
Спасибо и на этом )))

Сами алгоритмы уже являются хрестоматийными, ни для кого не секрет их временные сложности. Но интересно кто кого обгонит практике в абсолютном времени. Графики достаточно интересные, из которых можно сделать несколько занятных выводов. При этом, конечно, не стоит забывать что это применительно к PHP, на других языках картина была бы несколько иной.

1)Гномья сортировка, оказалась чуть медленнее чем вставками. Это очень похожие алгоритмы, мне всё было интересно кто из них быстрее.
Гном и вставки «заточены» под почти отсортированные массивы, было бы интересно если бы Вы протестировали на почти упорядоченных данных. Есть мнение, что в этом случае они обгонят даже быструю сортировку.

2)Неожиданно, что чётно-нечётная сортировка оказалась медленее, чем простой пузырёк. Чёт-нечет — это вроде как модифицированый пузырёк, ан вон оно как на самом деле.

3)Пирамидальная сортировка оказалась чуть быстрее чем сортировка слиянием. Тоже прикольно, обычно в тестах наоборот.

4)Ну и стоит обратить внимание на самую недооценённую сортировку — расчёской. По скорости уступает разве что легендарной быстрой сортировке, но при этом не все знают, что такой алгоритм вообще есть. А между тем «расчёска» — это всего-навсего «пузырёк» с уменьшающимся шагом.
Про сортировку слиянием действительно очень странно. Теоретически, она самая быстрая. Число сравнений у неё процентов на 10 меньше, чем у qsort, обменов (которые в 3-4 раза дороже простого копирования) нет вообще, и лишних копирований тоже нет (если правильно написать).
Может, влияют какие-то особенности интерпретируемых языков. Слияние наиболее прожорливо на дополнительную память.

Не берусь утверждать, насколько алгоритмы реализованы «правильно», выглядят вполне классически и стандартно.

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;
        }
}
Не знаю особенностей этого языка, но не приводит ли строчка
                $tmp = array();

в MergeSort к созданию нового динамического массива при каждом вызове функции? В С-образных языках такое приводило бы к замедлению в несколько раз.
Так и есть.

Причём, конкретно в PHP массивы с одной стороны — исключительно гибкие инструменты, но, как расплата за многие возможности — далеко не самое оптимизированное звено в программе. Вот про массивы в PHP хорошая хабрастатья.
ничего подобного, не падает
Извините, но графики в статье просто ужасны, очень сложно понять где что.
Но за статью спасибо.
Как я понял, автор взял те сортировки, которые есть в русской Википедии. А почему нет поразрядной сортировки (radix sort)? При чём интересно было бы сравнить между собой обе разновидности — MSD и LSD.
Для целочисленных массивов хорошо реализованная LSD в общем случае быстрее, чем MSD (не смотря на то, что теоретически должно быть наоборот). При этом для 32-битных чисел можно сделать LSD вариант, который обгоняет quiсksort уже при 60-70 элементах (я слышал и про более ранний обгон (30-40), но никогда не видел подобный код — там видимо хорошо проработанные SSE оптимизации используются).

И простите за оффтоп, но я просмотрел Ваш сайт про сортировки и там как раз в разделе про radix sort ошибка:
«Кроме того, MSD, в отличие от LSD, является устойчивым алгоритмом.» LSD безусловно является устойчивым алгоритмом, а вот как раз с MSD все не так просто. Наиболее быстрая in-place реализация не является устойчивой, а вот сделать такую же быструю реализацию устойчивой MSD сортировки с дополнительной памятью не получается на сколько я знаю.
Спасибо, в ближайшее время исправлю.
Насчёт того что LSD, быстрее чем MSD — действительно неожиданная информация.
Я конечно могу быть неправ, но усреднять значение по 3-м замерам, вероятно, маловато.
А уж если совсем придираться, то для таких вещей нужно говорить о доверительной вероятности результатов.
На мой взгляд графики стоило рисовать в логарифмических масштабах. Тогда бы не было такого слипания вблизи нуля.
Зачем нужна еще одна не идеальная статья о сортировках?
Стандартная сортировка ощутимо быстрее qsort… В гугле написано, что она использует её же, но мне кажется, что по скорости больше похоже на IntroSort
Интроспективная сортировка работает быстрее, только если подсунули массив-убийцу (специально подобранный массив являющийся для быстрой сортировки вырожденным случаем). В этом случае IntroSort переключается с использования QuickSort на HeapSort, что может ускорить процесс даже в сотни раз. На обычных массивах, даже очень больших, скорость будет примерно одинакова (маловероятно что массив случайно окажется вырожденным случаем), потому что IntroSort просто использует оптимизированную QuickSort.
Sign up to leave a comment.

Articles