В этой статье речь пойдёт о бенчмарке алгоритмов сортировки, написанном на PHP.
Всего представлено 14 алгоритмов:
Алгоритмы расположены не в алфавитном порядке, а в порядке уменьшения их быстродействия при сортировке массива в 8 тыс. элементов.
Представленные размерности массивов, использующиеся при сортировки:
Также каждый замер был произведён с различным наполнением массива, передающегося в функцию сортировки:
Каждый замер был сделан по три раза и взято среднее арифметическое.
В этой категории участвуют все функции сортировки.


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


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


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


QuickSort по праву считается достаточно хорошим алгоритмом. CountingSort очень хорош на небольших диапазонах значений, иначе не справляется из-за нехватки памяти. Шейкерная сортировка оказалась неудачным выбором для случайных значений. «Пузырьковая» и её модификации не применимы для практического использования.
Исходный код всех алгоритмов + мои результаты: drive.google.com/file/d/0B5FrhsQAeZwCUmx0dzFjeVdra0E/edit?usp=sharing
Всего представлено 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