Q04.2. What algorithm implementations are used in standart libraries of different programing languages?

[robertdubson]

Q04.2. What algorithm implementations are used in standart libraries of different programing languages? Q04.2. Які реалізації алгоритму сортування використовують стандартні бібліотеки різних мов?

[Rasim-I]

Python : TimSort Java : 1)for arrays of primitive data types : QuickSort; 2)for sorting Objects : MegreSort; 3)for collections : MergeSort. C++ : QuickSort and Qsort

(https://foxford.ru/wiki/informatika/standartnaya-sortirovka-v-python#) (https://ru.stackoverflow.com/questions/33385/) (https://codelessons.ru/cplusplus/funktsiya-sort-i-komparator-v-c-chto-eto-takoye.html)

[robertdubson]

У мові програмування Java для примітивних типів у Arrays використовується Quicksort. Для реалізації цього алгоритму сортування виділено клас DualPivotQuickSort, у якому визначено публічні методи sort для сортування даних. Методи Arrays API викликають ці методи та приймають посилання на масив. Якщо потрібно відосртувати якийсь діапазон масиву, то мають передаватися також відповідні індекси. У DualPivotQuickSort.sort також є додаткві алгоритми, які використовуються в залежності від типу даних, які зберігаються у масиві:

• для int, long, short, char, float, double (кількість елементів менше 47) використовуються insertion sort, pair insertion sort;
• для int, long, short, char, float, double(кількість елементів менше за 286) використується quick sort;
• для byte (кількість елементів більше за 29) використовується counting sort;
• для short, char (кількість елементів більше за 3200) використовуються counting sort

Джерело: https://habr.com/ru/post/344288/

[robertdubson]

У мові програмування Python у методі sorted() застосовується алгоритм TimSort: Timsort is a hybrid sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was invented by Tim Peters in 2002 for use in the Python programming language. The algorithm finds subsets of the data that are already ordered, and uses the subsets to sort the data more efficiently. This is done by merging an identified subset, called a run, with existing runs until certain criteria are fulfilled. Timsort has been Python's standard sorting algorithm since version 2.3. It is now also used to sort arrays in Java SE 7, and on the Android platform. (https://stackoverflow.com/questions/10948920/what-algorithm-does-pythons-sorted-use)

[khilchuk-ol]

В C# метод Array.Sort() працює наступним чином:

If the partition size is less than or equal to 16 elements, it uses an insertion sort algorithm.

If the number of partitions exceeds 2 * LogN, where N is the range of the input array, it uses a Heapsort algorithm.

Otherwise, it uses a Quicksort algorithm.

Ресурс: https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?redirectedfrom=MSDN&view=netcore-3.1#System_Array_Sort_System_Array_

[robertdubson]

У мові програмування C++ у методі std::sort прописана вбудована функція sort(). Вона використовує алгоритм IntroSort, який є об'єднанням алгоритмів QuickSort, Heapsort та InsertionSort. Також, у стандартній бібліотеці C є метод qsort(), який пропонується застусовувати для сортування масивів. Даний метод використовує Quicksort, що зрозуміло з назви. Але все одно, рекомандовано застосовувати метод sort() через наступні причини: -навідміну від метода qsort(), sort() не використовує небезпечні void-вказівники. -під час виконання програми метод qsort() викликає більше функцій, ніж sort(). -код програми мовою C++ працює швидше із використанням методу sort().

"The algorithm used by sort() is IntroSort. Introsort being a hybrid sorting algorithm uses three sorting algorithm to minimise the running time, Quicksort, Heapsort and Insertion Sort. Simply putting, it is the best sorting algorithm around. It is a hybrid sorting algorithm, which means that it uses more than one sorting algorithms as a routine. Standard C library provides qsort() that can be used for sorting an array. As the name suggests, the function uses QuickSort algorithm to sort the given array It is better to use sort() instead of qsort() because: sort() does not use unsafe void pointers like qsort(). qsort() makes large number of function calls for comparison function compared to sort(). C++ code with sort() is relatively faster than code with qsort()." Джерело: https://www.geeksforgeeks.org/internal-details-of-stdsort-in-c/

[glbter]

у мові програмування python (версія 3) для стандартних стуктур використовуються такі реалізації :

• list == linked list / array , хоча в сPython це массив
• set, frozenset == hash set
• dict == hash map ,

рекомендують перетворювати списки у множини, якщо потрібна велика кількість звернень до структури данних.