Бенчмарк 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 в текущей системе. На моей системе это значение 2⁶³, то есть около 9.2233720368548E+18

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

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

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

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

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

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

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

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

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

Выводы

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

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