Integer sorting (original) (raw)
In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are.
| Property | Value |
|---|---|
| dbo:abstract | In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are. Integer sorting algorithms including pigeonhole sort, counting sort, and radix sort are widely used and practical. Other integer sorting algorithms with smaller worst-case time bounds are not believed to be practical for computer architectures with 64 or fewer bits per word. Many such algorithms are known, with performance depending on a combination of the number of items to be sorted, number of bits per key, and number of bits per word of the computer performing the sorting algorithm. (en) En informatique, le tri de nombres entiers est le problème algorithmique consistant à trier une collection d'éléments au moyen de clés numériques, chacune étant un nombre entier. Les algorithmes conçus pour le tri des nombres entiers peuvent également souvent être appliqués aux problèmes de tri dans lesquels les clés sont des nombres décimaux, des nombres rationnels ou des chaînes de texte. La possibilité d'effectuer une arithmétique sur les clés permet aux algorithmes de tri d'entiers d'être plus rapides que les algorithmes de tri par comparaison, en fonction du détail des opérations autorisées dans le modèle de calcul et de la taille des entiers à trier. Les algorithmes de tri de nombres entiers, notamment le , le tri comptage et le tri par base, sont largement utilisés et pratiques. D'autres algorithmes de tri de nombres entiers avec des limites de temps plus faibles dans le pire des cas ne sont pas considérés comme pratiques pour les architectures informatiques à 64 bits ou moins. Beaucoup de ces algorithmes sont connus, les performances dépendant du nombre d'éléments à trier, du nombre de bits par clé et du nombre de bits par mot de l'ordinateur exécutant l'algorithme de tri. (fr) Цілочисельне сортування в інформатиці — це алгоритмічна задача сортування набору значень за числовими ключами, кожен з яких є цілим числом. Алгоритми, призначені для цілочисельного сортування, також можуть часто застосовуватися до задач сортування, в яких ключі — числа з рухомою комою, раціональні числа або текстові рядки. В багатьох випадках можливість виконання цілочисельної арифметики з ключами дозволяє цілочисельним алгоритмам сортування виконуватись швидше, ніж алгоритмам сортування порівняннями, але це залежить від того, які операції дозволені в моделі обчислень і наскільки великими можуть бути цілі числа. Широко використовуються практичні алгоритми цілочисельного сортування, такі як сортування Діріхле (англ. Pigeonhole), сортування підрахунком і сортування за розрядами. Інші алгоритми цілочисельного сортування, з меншими оцінками найгіршого випадку, не вважаються практичними для комп'ютерних архітектур, які мають 64 й менше бітів на слово. Відомо багато таких алгоритмів, швидкодія яких залежить від комбінації кількості об'єктів, що підлягають сортуванню, кількості бітів на ключ і кількості бітів на слово у комп'ютері, який виконує алгоритм сортування. (uk) Целочисленная сортировка — задача сортировки некоторого набора значений при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений операций и величины чисел-ключей. Обычные алгоритмы целочисленной сортировки: корзинная сортировка, поразрядная сортировка, сортировка подсчётом широко распространены и эффективны. Дальнейшие исследования алгоритмов целочисленной сортировки были направлены на теоретические улучшения худшего случая, а алгоритмы, которые были получены, не считаются эффективными для современных 64-битных компьютеров, хотя эксперименты показали, что некоторые из этих методов могут быть лучше поразрядной сортировки данных со 128 и более битами на ключ. Кроме того, для больших наборов данных почти произвольный характер доступа к памяти алгоритмов целочисленной сортировки является ограничением, особенно в сравнении с другими алгоритмами сортировок, которые были разработаны с учётом иерархичной структуры памяти. Целочисленная сортировка используется в одном из шести эталонных тестов в наборе DARPA High Productivity Computing Systems Discrete Mathematics и в одном из одиннадцати критериев NAS Parallel Benchmarks suite. (ru) |
| dbo:wikiPageExternalLink | http://www.diku.dk/forskning/performance-engineering/Publications/pedersen99.ps https://books.google.com/books%3Fid=i3S9_GnHZwYC&pg=PA278 https://web.archive.org/web/20120316082511/http:/www.diku.dk/forskning/performance-engineering/Publications/pedersen99.ps http://portal.acm.org/citation.cfm%3Fid=644221 http://www.usenix.org/publications/compsystems/1993/win_mcilroy.pdf https://www.cs.ru.nl/~elenam/WAEMS.pdf |
| dbo:wikiPageID | 31552761 (xsd:integer) |
| dbo:wikiPageLength | 32140 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1109928117 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:64-bit dbr:Power_of_two dbr:Memory_access_pattern dbr:Benchmark_(computing) dbr:Binary_heap dbr:Algorithm dbr:Van_Emde_Boas_tree dbr:Information_Processing_Letters dbr:Information_and_Computation dbr:Pentium dbr:Max_Planck_Institute_for_Computer_Science dbr:McGraw-Hill dbr:NAS_Parallel_Benchmarks dbr:MIT_Press dbr:Comparison_sort dbr:Computer_science dbr:Pigeonhole_sort dbr:Priority_queue dbr:Prefix_sum dbr:Theoretical_Computer_Science_(journal) dbr:B-tree dbr:Bucket_queue dbc:Sorting_algorithms dbr:Trie dbr:Fusion_tree dbr:Linear_network_coding dbr:Linked_list dbr:DARPA dbr:Cell-probe_model dbr:Iterated_logarithm dbr:Journal_of_Computer_and_System_Sciences dbr:Journal_of_the_ACM dbr:Ken_Batcher dbr:Floating_point dbr:Radix dbr:Hash_table dbr:High_Productivity_Computing_Systems dbr:Counting_sort dbr:Bit_field dbr:Bitonic_sorter dbr:Collection_(abstract_data_type) dbr:Positional_notation dbr:Sorting_algorithm dbr:Integer dbr:Merge_algorithm dbr:Merge_sort dbr:Radix_sort dbr:Rational_number dbr:Selection_sort dbr:Memory_hierarchy dbr:Model_of_computation dbr:Y-fast_trie dbr:External_memory_algorithm dbr:Pointer_machine dbr:Parallel_random_access_machine dbr:Transdichotomous_model dbr:Word_RAM dbr:Worst_case_analysis dbr:Worst_case dbr:Heap_sort dbr:Bitvector dbr:Random_access_machine |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Good_article dbt:Harvtxt dbt:Math dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sqrt |
| dcterms:subject | dbc:Sorting_algorithms |
| gold:hypernym | dbr:Problem |
| rdf:type | yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Disease yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | In computer science, integer sorting is the algorithmic problem of sorting a collection of data values by integer keys. Algorithms designed for integer sorting may also often be applied to sorting problems in which the keys are floating point numbers, rational numbers, or text strings. The ability to perform integer arithmetic on the keys allows integer sorting algorithms to be faster than comparison sorting algorithms in many cases, depending on the details of which operations are allowed in the model of computing and how large the integers to be sorted are. (en) En informatique, le tri de nombres entiers est le problème algorithmique consistant à trier une collection d'éléments au moyen de clés numériques, chacune étant un nombre entier. Les algorithmes conçus pour le tri des nombres entiers peuvent également souvent être appliqués aux problèmes de tri dans lesquels les clés sont des nombres décimaux, des nombres rationnels ou des chaînes de texte. La possibilité d'effectuer une arithmétique sur les clés permet aux algorithmes de tri d'entiers d'être plus rapides que les algorithmes de tri par comparaison, en fonction du détail des opérations autorisées dans le modèle de calcul et de la taille des entiers à trier. (fr) Целочисленная сортировка — задача сортировки некоторого набора значений при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений операций и величины чисел-ключей. (ru) Цілочисельне сортування в інформатиці — це алгоритмічна задача сортування набору значень за числовими ключами, кожен з яких є цілим числом. Алгоритми, призначені для цілочисельного сортування, також можуть часто застосовуватися до задач сортування, в яких ключі — числа з рухомою комою, раціональні числа або текстові рядки. В багатьох випадках можливість виконання цілочисельної арифметики з ключами дозволяє цілочисельним алгоритмам сортування виконуватись швидше, ніж алгоритмам сортування порівняннями, але це залежить від того, які операції дозволені в моделі обчислень і наскільки великими можуть бути цілі числа. (uk) |
| rdfs:label | Integer sorting (en) Tri de nombres entiers (fr) 정수 정렬 (ko) Целочисленная сортировка (ru) Цілочисельне сортування (uk) |
| owl:sameAs | freebase:Integer sorting yago-res:Integer sorting wikidata:Integer sorting http://bn.dbpedia.org/resource/পূর্ণসংখ্যা_শ্রেণীকরণ dbpedia-fr:Integer sorting dbpedia-ko:Integer sorting dbpedia-ru:Integer sorting dbpedia-sr:Integer sorting dbpedia-uk:Integer sorting https://global.dbpedia.org/id/LsZ4 |
| prov:wasDerivedFrom | wikipedia-en:Integer_sorting?oldid=1109928117&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Integer_sorting |
| is dbo:wikiPageRedirects of | dbr:Integer_sort |
| is dbo:wikiPageWikiLink of | dbr:Quicksort dbr:Van_Emde_Boas_tree dbr:Maxima_of_a_point_set dbr:NAS_Parallel_Benchmarks dbr:Convex_hull_algorithms dbr:Dan_Willard dbr:Comparison_sort dbr:Prefix_sum dbr:Widest_path_problem dbr:Predecessor_problem dbr:Counting_sort dbr:Real_RAM dbr:Sorting_algorithm dbr:Transdichotomous_model dbr:Word_RAM dbr:Random_access dbr:X_+_Y_sorting dbr:Integer_sort |
| is foaf:primaryTopic of | wikipedia-en:Integer_sorting |