Q04.2. What sorting implementations are used by standard libraries in different languages?

[vldnik]

What sorting implementations are used by standard libraries in different languages? Які реалізації алгоритму сортування використовують стандартні бібліотеки різних мов?

Not only standard or built-in libraries for this language, but also other popular libraries If certain languages / libraries support several implementations – please describe which ones are more popular and provide a link to the guidelines for the choice Please provide links/references supporting your answer.

Можна не лише стандартні чи вбудовані бібліотеки для даної мови, а й інші популярні бібліотеки Якщо певні мови/бібліотеки підтримують кілька реалізацій – бажано описати, які з них є більш популярними, та навести посилання на рекомендації щодо вибору Необхідно обов'язково навести посилання на ресурси, що підтверджують відповіді.

[NvkAnton]

У Java, Collections.sort() використовує Merge sort. Arrays.sort() використовує два алгоритма сортування: Quick sort та Merge sort.

У Python, в sorted() використовується Tim sort

[FairyFox5700]

У мові С++ під стандартним методом сортування використовується QuickSort. Джерело : https://www.geeksforgeeks.org/sort-algorithms-the-c-standard-template-library-stl/ Для сортування списку в мові C# використовують Insertion sort, якщо розмір масиву менше ніж 16 елементів. Якщо кількість поділів(partition) перевищує 2 * log(n), застосовується Heapsort. В усіх інших випадках застосовують Quicksort. Підтверженням є сторінка з документації : https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.8 Також в цій мові реалізований Binary Search алгоритм, який доцільно використовувати на впорядкованому масиві. Детальніше за посиланням : https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.binarysearch?view=netframework-4.8

[kzhereb]

У Java, Collections.sort() використовує Merge sort. Arrays.sort() використовує два алгоритма сортування: Quick sort та Merge sort.

У Python, в sorted() використовується Tim sort

У мові С++ під стандартним методом сортування використовується QuickSort. Для сортування списку в мові C# використовують Insertion sort, якщо розмір масиву менше ніж 16 елементів. Якщо кількість поділів(partition) перевищує 2 * log(n), застосовується Heapsort. В усіх інших випадках застосовують Quicksort. Також в цій мові реалізований Binary Search алгоритм, який доцільно використовувати на впорядкованому масиві.

Прохання надати посилання на відповідні ресурси, що підтверджують відповіді (тобто описують, що в цих мовах чи бібліотеках використано саме такі алгоритми) - без цього відповіді не будуть зараховані

[Tia333]

Java: Є два вбудованих методу сортування в Java: Arrays.Sort () працює для массивов, які також можуть використовувати примитивний тип даних; Collections.sort () працює з об'єктами Collections, такими як ArrayList і LinkedList. Посилання: https://www.geeksforgeeks.org/sorting-in-java/

C#: Для сортування зв'язаного списку часто обираэться Merge sort. Низька продуктивність зв'язаного списку з випадковим доступом робить деякі інші алгоритми (наприклад, quicksort) неефективними, а інші (наприклад, heapsort) абсолютно неможливі. Посилання: https://www.geeksforgeeks.org/merge-sort-linked-lists-javascript/

Python: У Numpy ми можемо виконувати різні операції сортування, використовуючи різні функції, які надаються у бібліотеці, наприклад сортування, lexsort, argsort і т.д.

• numpy.sort (): Ця функція повертає сортовану копію масиву.
• numpy.argsort (): Ця функція повертає індекси, які сортують масив.
• numpy.lexsort (): Ця функція повертає непрямий стабільний сорт за допомогою послідовності ключів.

Посилання: https://www.geeksforgeeks.org/numpy-sorting-searching-and-counting/

[carolinepi]

C++: There are std::sort, std::stable_sort, std::partial_sort and etc. in C++. The std::sort is a sorting function that uses the Introsort algorithm and have the complexity of O(N log(N)). The std::stable_sort uses Merge Sort algorithm and has time complexity of O(N log(N)²) . The std::partial_sort function uses the Heapsort algorithm, that is a binary tree based sorting algorithm. Link: https://medium.com/@lucianoalmeida1/exploring-some-standard-libraries-sorting-functions-dd633f838182

[ghost]

https://habr.com/ru/post/344288/

[P0linux]

C#: You can also sort collections and arrays using LINQ(Language Integrated Query) which is the name for a set of technologies based on the integration of query capabilities directly into the C# language. The method is OrderBy (sort in ascending order) or OrderByDescending(sort in descending order). It implements QuickSort, but the reason why it is stable is because the indices of each pair of elements are compared if all the keys test equal. Complexity of the sort operation stays the typical for QuickSort O(N*logN) average / O(N2) worst case. Pros: intuitively similar to queries of the SQL language, simple access to data. It is more rationally to use LINQ query to access data sourses: MS SQL Server, Data Sets, XML files. Sometimes LINQ query can make the code simpler. More information: https://docs.microsoft.com/ru-ru/dotnet/csharp/programming-guide/concepts/linq/ https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.orderby?view=netframework-4.8 https://stackoverflow.com/questions/2792074/what-sorting-algorithm-is-used-by-linq-orderby/2792105#2792105

[WalrusPUNCH]

C#: List.Sort Method This method uses Array.Sort, which applies the introspective sort as follows:

• If the partition size is fewer than 16 elements, it uses an insertion sort algorithm
• If the number of partitions exceeds 2 log n, where n is the range of the input array, it uses a Heapsort algorithm.
• Otherwise, it uses a Quicksort algorithm.

This implementation performs an unstable sort. On average, this method is an O(n log n) operation, where n is Count; in the worst case it is an O(n^2) operation.

Source: https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.list-1.sort?view=netframework-4.8

C++ Merge sort used in stable_sort function from STL.

[illix-it]

C does not specificy the algorithm to be used by qsort.

On current glibc (2.17) qsort allocates memory (using malloc or alloca if memory required is really small) and uses merge sort algorithm. If memory requirements are too high or if malloc fails it uses quicksort algorithm.

The qsort() and qsort_r() functions are an implementation of C.A.R. Hoare's "quicksort" algorithm, a variant of partition-exchange sorting; in particular, see D.E. Knuth's Algorithm Q. Quicksort takes O(n lg n) average time. This implementation uses median selection to avoid its O(n2) worst-case behavior.

The heapsort() function is an implementation of J.W.J. William's "heapsort" algorithm, a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. Heapsort takes O(n lg n) worst-case time. Its only advantage over qsort() is that it uses almost no additional memory; while qsort() does not allocate memory, it is implemented using recursion.

The function mergesort() requires additional memory of size nel * width bytes; it should be used only when space is not at a premium. The mergesort() function is optimized for data with pre-existing order; its worst case time is O(n lg n); its best case is O(n).

Normally, qsort() is faster than mergesort() which is faster than heapsort(). Memory availability and pre-existing order in the data can make this untrue.

[AleksAndriushyn]

Java and Python both look like they make use of timsort in their standard libaries, while the sorting method in C's stdlib is called qsort because it once was quicksort.

The important thing to derive from reading the standard is that qsort has no interface to report failure and thus is not allowed to return without sorting the input. This basically restricts implementors to either using in-place algorithms, or providing a fallback in-place algorithm when memory allocation fails.

[NikitaViktorov]

Python: У Numpy ми можемо виконувати різні операції сортування, використовуючи різні функції, які надаються у бібліотеці, наприклад сортування, lexsort, argsort і т.д.

numpy.sort (): Ця функція повертає сортовану копію масиву. numpy.argsort (): Ця функція повертає індекси, які сортують масив. numpy.lexsort (): Ця функція повертає непрямий стабільний сорт за допомогою послідовності ключів.

[invisy]

У мові програмування C# сортування відбувається за допомогою комбінації різних алгоритмів сортування. Наприклад, метод Sort(Array, Int32, Int32) використовує алгоритм сортування вставками до 16 елементів, якщо число секцій перевищує 2 * журнала^N, де N діапазон вхідного массиву, він використовує Heapsort. У всіх інших випадках використовується QuickSort. https://docs.microsoft.com/en-us/dotnet/api/system.array.sort?view=netframework-4.8

Вбудований метод в Python sorted() використовує Timsort. https://docs.python.org/3/howto/sorting.html

В C++ метод std::sort() алгоритм має складність O(nlogn) в будь-якому випадку(офіційна документація). За неофіційними даними, цю складність забезпечує алгоритм Intro Sort, який включає в себе Quicksort, Heapsort і Insertion Sort. https://ru.cppreference.com/w/cpp/algorithm/sort https://www.geeksforgeeks.org/internal-details-of-stdsort-in-c/

[galaxyair]

Swift: Instance Method sorted(by:) Returns the elements of the sequence, sorted using the given predicate as the comparison between elements.

Source: https://developer.apple.com/documentation/swift/array/2296815-sorted

[BogdanDudnik]

C#: Для сортування зв'язаного списку часто обираэться Merge sort. Низька продуктивність зв'язаного списку з випадковим доступом робить деякі інші алгоритми (наприклад, quicksort) неефективними, а інші (наприклад, heapsort) абсолютно неможливі. Посилання: https://www.geeksforgeeks.org/merge-sort-linked-lists-javascript/

[Pawtetka]

C#: You can also sort collections and arrays using LINQ(Language Integrated Query) which is the name for a set of technologies based on the integration of query capabilities directly into the C# language. The method is OrderBy (sort in ascending order) or OrderByDescending(sort in descending order). It implements QuickSort, but the reason why it is stable is because the indices of each pair of elements are compared if all the keys test equal. Complexity of the sort operation stays the typical for QuickSort O(N*logN) average / O(N2) worst case. Pros: intuitively similar to queries of the SQL language, simple access to data. It is more rationally to use LINQ query to access data sourses: MS SQL Server, Data Sets, XML files. Sometimes LINQ query can make the code simpler. More information: https://docs.microsoft.com/ru-ru/dotnet/csharp/programming-guide/concepts/linq/ https://docs.microsoft.com/en-us/dotnet/api/system.linq.enumerable.orderby?view=netframework-4.8 https://stackoverflow.com/questions/2792074/what-sorting-algorithm-is-used-by-linq-orderby/2792105#2792105