Бенчмарк 14 алгоритмів сортування на масивах з різною розмірністю і вмістом

Бенчмарк 14 алгоритмів сортування на масивах з різною розмірністю і вмістом

У цій статті мова піде про бенчмарку алгоритмів сортування, написаному на PHP.

Всього представлено 14 алгоритмів:

  • quickSort
  • countingSort
  • combSort
  • heapSort
  • mergeSort
  • shellSort
  • selectionSort
  • insertSort
  • gnomeSort
  • combinedBubbleSort
  • cocktailSort
  • bubbleSort
  • oddEvenSort
  • bubbleSortWithFlag

Докладніше про алгоритми

quickSort - Швидке сортування *

countingSort - Сортування підрахунком *

combSort - Впорядкування розрахункової *

heapSort - Сортування купою *

mer  Sort - Сортування злиттям *

shellSort - Сортування Шелла *

selec  Sort - Впорядкування вибором *

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, тобто близько2233720368548E + 18

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

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

У цій категорії беруть участь всі функції сортування.

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

Цього разу беруть участь 5 найшвидших алгоритми: сортування підрахунком, швидке сортування, сортування розрахункової, сортування купою і сортування злиттям.

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

Цього разу беруть участь все ті ж 5 алгоритмів: сортування підрахунком, швидке сортування, сортування розрахункової, сортування купою і сортування злиттям.

Масиви до 2.000.000 елементів

В останньому забігу на 2 мільйони елементів взяли участь два алгоритми: впорядкування підрахунком і швидке сортування.

Висновки

QuickSort по праву вважається досить хорошим алгоритмом. CountingSort дуже хороший на невеликих діапазонах значень, інакше не справляється через брак пам'яті. Шейкерне сортування виявилося невдалим вибором для випадкових значень. «Бульбашкова» і її модифікації не застосовні для практичного використання.

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