[Из песочницы] Бенчмарк 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
