В этой статье основное внимание будет уделено тестированию алгоритмов сортировки, написанных на PHP. Всего представлено 14 алгоритмов:
- быстрая сортировка
- подсчетСортировка
- объединитьСортировать
- пирамидальная сортировка
- Сортировка слиянием
- ShellSort
- выборСортировка
- вставкасортировка
- gnomeSort
- комбинированная сортировка пузырьком
- коктейльСорт
- пузырьковая сортировка
- нечетныйEvenSort
- bubbleSortWithFlag
| QuickSort – Быстрая сортировка * |
| countingSort – сортировка подсчетом * |
| comSort – гребенчатая сортировка. |
| heapSort – пирамидальная сортировка * |
| mergeSort – сортировка слиянием * |
| ShellSort – Сортировка Шелла * |
| selectionSort – сортировка по выбору * |
| InsertSort – сортировка вставками * |
| gnomeSort – сортировка «Gnome» * |
| комбинированная сортировка BubbleSort – модифицированная сортировка «пузырьком».
|
| CocktailSort – сортировка «Шейкер» * |
| bubbleSort – сортировка «пузырем» * |
| нечетная сортировка – четно-нечетная сортировка |
| bubbleSortWithFlag – сортировка «пузырьком» с флагом перестановки.
|
Представлены размеры массива, используемые для сортировки:
- 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 63 , то есть о 9.2233720368548E+18
Массивы до тысячи элементов
Все функции сортировки включены в эту категорию.
Массивы до 30 тысяч элементов
На этот раз задействованы 5 самых быстрых алгоритмов: сортировка подсчетом, быстрая сортировка, гребенчатая сортировка, сортировка кучей и сортировка слиянием.
Массивы до 200 тысяч элементов
На этот раз задействованы те же 5 алгоритмов: сортировка подсчетом, быстрая сортировка, гребенчатая сортировка, пирамидальная сортировка и сортировка слиянием.
Массивы размером до 2 000 000 элементов.
Последний прогон с 2 миллионами элементов включал два алгоритма: сортировку подсчетом и быструю сортировку.
выводы
Быстрая сортировка по праву считается достаточно хорошим алгоритмом.ПодсчетСортировка очень хорошо для небольших диапазонов значений, иначе не получится из-за нехватки памяти.
Шейкерная сортировка оказался плохим выбором для случайных значений.
«Пузырь» и его модификации неприменим для практического использования.
Исходный код всех алгоритмов + мои результаты: Drive.google.com/file/d/0B5FrhsQAeZwCUmx0dzFjeVdra0E/editЭusp=sharing Теги: #benchmarks #benchmark #алгоритмы сортировки #php #Алгоритмы
-
Материя Состоит Из Пустоты Или 0,(9)=1
19 Oct, 24 -
Как Перетащить Картинку Из Ms Word
19 Oct, 24 -
Саундтрек №42
19 Oct, 24 -
Второе Знакомство С Ос Inferno
19 Oct, 24
