Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 29.05.2014 | нет комментариев

В этой статье речь пойдёт о бенчмарке алгорифмов сортировки, написанном на 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

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB