| 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)
|
| 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)
|
