Пользователь
0,0
рейтинг
6 мая 2014 в 13:24

Разработка → Бенчмарк 14 алгоритмов сортировки на массивах с разной размерностью и содержанием из песочницы

В этой статье речь пойдёт о бенчмарке алгоритмов сортировки, написанном на PHP.

Всего представлено 14 алгоритмов:

  • quickSort
  • countingSort
  • combSort
  • heapSort
  • mergeSort
  • shellSort
  • selectionSort
  • insertSort
  • gnomeSort
  • combinedBubbleSort
  • cocktailSort
  • bubbleSort
  • oddEvenSort
  • bubbleSortWithFlag


Подробнее об алгоритмах
quickSort – Быстрая сортировка*
countingSort – Сортировка подсчетом*
combSort – Сортировка расчёской*
heapSort – Сортировка кучей*
mergeSort – Сортировка слиянием*
shellSort – Сортировка Шелла*
selectionSort – Сортировка выбором*
insertSort – Сортировка вставками*
gnomeSort – «Гномья» сортировка*
combinedBubbleSort – Модифицированная «Пузырьковая» сортировка
cocktailSort – «Шейкерная» сортировка*
bubbleSort – «Пузырьковая» сортировка*
oddEvenSort – Сортировка чёт-нечет
bubbleSortWithFlag – «Пузырьковая» сортировка с флагом перестановок



Алгоритмы расположены не в алфавитном порядке, а в порядке уменьшения их быстродействия при сортировке массива в 8 тыс. элементов.

Представленные размерности массивов, использующиеся при сортировки:

  • 1
  • 100
  • 200
  • 400
  • 600
  • 800
  • 1000
  • 5000
  • 10000
  • 15000
  • 20000
  • 25000
  • 30000


Также каждый замер был произведён с различным наполнением массива, передающегося в функцию сортировки:

  • В первом случае массив заполнялся случайными значениями из промежутка (1, n), где n — размерность массива.
  • Во втором случае массив заполнялся случайными значениями из промежутка (1, PHP_INT_MAX), где PHP_INT_MAX — максимальное значения переменной типа INT в текущей системе. На моей системе это значение 263, то есть около 9.2233720368548E+18


Каждый замер был сделан по три раза и взято среднее арифметическое.

Массивы размерностю до тысячи элементов


В этой категории участвуют все функции сортировки.




Массивы размерностью до 30 тысяч элементов


В этот раз участвуют 5 самых быстрых алгоритма: сортировка подсчётом, быстрая сортировка, сортировка расчёской, сортировка кучей и сортировка слиянием.




Массивы размерностью до 200 тысяч элементов


В этот раз участвуют все те же 5 алгоритмов: сортировка подсчётом, быстрая сортировка, сортировка расчёской, сортировка кучей и сортировка слиянием.




Массивы размерностью до 2.000.000 элементов


В последнем забеге на 2 миллиона элементов приняли участие два алгоритма: сортировка подсчётом и быстрая сортировка.




Выводы


QuickSort по праву считается достаточно хорошим алгоритмом. CountingSort очень хорош на небольших диапазонах значений, иначе не справляется из-за нехватки памяти. Шейкерная сортировка оказалась неудачным выбором для случайных значений. «Пузырьковая» и её модификации не применимы для практического использования.

Исходный код всех алгоритмов + мои результаты: drive.google.com/file/d/0B5FrhsQAeZwCUmx0dzFjeVdra0E/edit?usp=sharing
@ahwoobachairiesaas
карма
1,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (21)

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

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

    Сами алгоритмы уже являются хрестоматийными, ни для кого не секрет их временные сложности. Но интересно кто кого обгонит практике в абсолютном времени. Графики достаточно интересные, из которых можно сделать несколько занятных выводов. При этом, конечно, не стоит забывать что это применительно к 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
          Не знаю особенностей этого языка, но не приводит ли строчка
                          $tmp = array();
          

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

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

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

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.