Q04.3. Benchmarks for sorting algorithms

[vldnik]

Benchmarks for sorting algorithms Benchmarks для алгоритмів сортування

Provide resources that compare the performance of different sorting algorithms and their implementations Can be a comparison for standard operations, or for the implementation of specific tasks Consider different cases – random arrays, almost sorted, … Bonus points if benchmarks available – to run on your own devices

Навести ресурси з порівнянням продуктивності різних алгоритмів сортування Може бути порівняння в загальному випадку, або для реалізації конкретних задач Бажано, щоб розглядались різні випадки – випадкові масиви, майже відсортовані, … Бажано, щоб був доступний код benchmarks – щоб можна було запустити на своїх пристроях

[NvkAnton]

https://m.habr.com/ru/post/335920/

[FairyFox5700]

http://ddeville.me/2010/10/sorting-algorithms-comparison Розглядаються випадки коли масив випадково відсортовано, відсортовано у звичайному та у зворотньому порядках. Порівнюються складність з часовими показниками відповідно до розміру масиву. https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html - сайт з візуалізацією деяких алгоритмів сортування.

[LiliaTumanova]

https://github.com/arisath/Benchmarking-Sorting-Algorithms

[Tia333]

• Порівняльний аналіз алгоритмів сортування by Alejandro Erickson - http://alejandroerickson.com/j/2016/08/02/benchmarking-int-sorting-algorithms.html
• Visualization and Comparison of Sorting Algorithms - https://www.youtube.com/watch?v=ZZuD6iUe3Pc

[Kostiantun]

Залежність складності алгоритмів сортування від впорядкованості елементів : https://hashanp.xyz/algorithms.html

[WalrusPUNCH]

Порівняння алгоритмів сортування з книги "Algorithms in a Nutshell", 2nd Edition. Автори: Stanley Selkow, Gary Pollice, George T. Heineman https://www.oreilly.com/library/view/algorithms-in-a/9781491912973/ch04.html

Good article about choosing and comparing of sorting algorithms. https://www.interviewcake.com/sorting-algorithm-cheat-sheet

Also, here is interesting gif which represents visualization of sorting algorithms. https://www.reddit.com/r/interestingasfuck/comments/3cme6b/sorting_algorithms_visualised/

[IlliaKov]

Here is some info about it: Benchmark inputs

“What is the best sorting algorithm?” I have seen this question a dozen times, and the best answer is, invariably: it depends what you are sorting. Not only does it depend on the length of the input array, it also depends on how sorted you expect it to be in the first place, and whether or not the array values are bounded. For example, insertion sort is worst case quadratic, but it’s still extremely fast for long arrays that are already nearly sorted. It’s also faster than it’s asymptotically better counterparts on very short input arrays. For arrays with only small values, radix sort (with counting sort as a subroutine) provides near-linear sort-time. What if you have many small values and a few large ones?

Choosing the best sorting algorithm is as much about knowing what you sorting as it is about the relative performance of the algorithms.

What, then, are some good benchmarks? A lot of data “in the wild” is already sorted, either mostly or completely, so (mostly) pre-sorted inputs are a must. The sort order of the data might also be opposite the sort order of the sorting algorithm, and in many cases this is the difference between best and worst case performance. We already have five benchmark properties to try:

Unsorted Sorted Mostly sorted Reverse sorted Reverse mostly sorted

[crowl1]

Сортування в Python https://stackabuse.com/sorting-algorithms-in-python/

[AleksAndriushyn]

Good article about choosing and comparing of sorting algorithms: https://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

[NikitaViktorov]

https://www.youtube.com/watch?v=ZZuD6iUe3Pc

[galaxyair]

Quicksort Best: Ω(n log(n)) Worst: O(n^2) Mergesort Best: Ω(n log(n)) Worst: O(n log(n)) Timsort Best: Ω(n) Worst: O(n log(n))

[BogdanDudnik]

Хороша стаття про вибір та порівняння алгоритмів сортування: https://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html