Pull to refresh

Бенчмарк 14 алгоритмов сортировки на массивах с разной размерностью и содержанием

Reading time 2 min
Views 37K
В этой статье речь пойдёт о бенчмарке алгоритмов сортировки, написанном на 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
Tags:
Hubs:
+2
Comments 21
Comments Comments 21

Articles