Целочисленная сортировка

Целочисленная сортировка — задача сортировки некоторого набора значений при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений операций и величины чисел-ключей.

Обычные алгоритмы целочисленной сортировки: корзинная сортировка, поразрядная сортировка, сортировка подсчётом широко распространены и эффективны. Дальнейшие исследования алгоритмов целочисленной сортировки были направлены на теоретические улучшения худшего случая, а алгоритмы, которые были получены, не считаются эффективными для современных 64-битных компьютеров, хотя эксперименты показали, что некоторые из этих методов могут быть лучше поразрядной сортировки данных со 128 и более битами на ключ. Кроме того, для больших наборов данных почти произвольный характер доступа к памяти алгоритмов целочисленной сортировки является ограничением, особенно в сравнении с другими алгоритмами сортировок, которые были разработаны с учётом иерархичной структуры памяти.

Целочисленная сортировка используется в одном из шести эталонных тестов в наборе DARPA High Productivity Computing Systems Discrete Mathematics и в одном из одиннадцати критериев NAS Parallel Benchmarks suite.

Модели вычислений

Временные ограничения алгоритмов целочисленной сортировки обычно зависят от трех параметров: $n$ — количество значений данных, которые должны быть отсортированы, $K$ — порядок величины максимально возможного ключа и $W$ — число бит в машинном слове компьютера, на котором алгоритм будет выполняться. Как правило, полагается, что $W\geqslant \log _{2}\max(n,K)$, то есть, машинные слова достаточно большие, чтобы представлять как индекс в последовательности входных данных, так и ключ.

Алгоритмы целочисленной сортировки, как правило, разрабатываются для работы либо для машины указателей, либо для машины с произвольным доступом к памяти. Основное различие этих моделей заключается в том, что машины с произвольным доступом позволяют использовать произвольное значение в регистре в качестве адреса памяти в операциях чтения и записи с единичной временной стоимостью, а сложные манипуляции с данными организовать с помощью таблицы поиска. Модель машины указателей позволяет доступ к памяти только через указатели, которыми нельзя манипулировать путём арифметических операций. В обеих моделях побитовые операции могут быть выполнены, как правило, за один квант времени. Различные алгоритмы целочисленной сортировки делают разные предположения о том, можно ли выполнять целочисленное умножение за один квант времени. Могут рассматриваться и более специализированные модели вычислений, такие как параллельные машины с произвольным доступом.

В 1999 году показано, что в некоторых случаях умножение или табличный поиск, необходимый для некоторых алгоритмов целочисленной сортировки, можно заменить на специализированные операции, которые могут быть легко реализованы аппаратными средствами, но обычно недоступны на компьютерах общего назначения.

Литература

• Ajtai, M., Fredman, M., Komlós, J. Hash functions for priority queues (англ.) // Information and Control. — 1984. — Vol. 63, no. 3. — P. 217–225. — doi:10.1016/S0019-9958(84)80015-7.
• Albers, Susanne, Hagerup, Torben. Improved parallel integer sorting without concurrent writing (англ.) // Information and Computation. — 1997. — Vol. 136, no. 1. — P. 25–51. — doi:10.1006/inco.1997.2632.
• Andersson, Arne, Hagerup, Torben, Nilsson, Stefan, Raman, Rajeev. Sorting in linear time? (англ.) // Journal of Computer and System Sciences. — 1998. — Vol. 57, no. 1. — P. 74–93. — doi:10.1006/jcss.1998.1580.
• Andersson, Arne, Nilsson, Stefan. Implementing radixsort (англ.) // The ACM Journal of Experimental Algorithmics. — 1998. — Vol. 3. — doi:10.1145/297096.297136.
• Andersson, Arne, Miltersen, Peter Bro, Thorup, Mikkel. Fusion trees can be implemented with AC⁰ instructions only (англ.) // Theoretical Computer Science. — 1999. — Vol. 215, no. 1—2. — P. 337–344. — doi:10.1016/S0304-3975(98)00172-8.
• Bhatt, P. C. P., Diks, K., Hagerup, T., Prasad, V. C., Radzik, T., Saxena, S. Improved deterministic parallel integer sorting (англ.) // Information and Computation. — 1991. — Vol. 94, no. 1. — P. 29–47. — doi:10.1016/0890-5401(91)90031-V.
• Cole, R., Vishkin, u. Deterministic coin tossing with applications to optimal parallel list ranking (англ.) // Information and Control. — 1986. — Vol. 70, no. 1. — P. 32–53. — doi:10.1016/S0019-9958(86)80023-7.
• Comrie, L. J. The Hollerith and Powers tabulating machines (англ.) // Trans. Office Mach. Users’ Assoc., Ltd. — 1929–1930. — P. 25–37.
• Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L., Stein, Clifford. Introduction to Algorithms (англ.). — MIT Press and McGraw-Hill, 2001.
• Fredman, Michael L., Willard, Dan E. Surpassing the information-theoretic bound with fusion trees (англ.) // Journal of Computer and System Sciences. — 1993. — Vol. 47, no. 3. — P. 424–436. — doi:10.1016/0022-0000(93)90040-4.
• Fredman, Michael L., Willard, Dan E. Trans-dichotomous algorithms for minimum spanning trees and shortest paths (англ.) // Journal of Computer and System Sciences. — 1994. — Vol. 48, no. 3. — P. 533–551. — doi:10.1016/S0022-0000(05)80064-9.
• Goodrich, Michael T., Tamassia, Roberto. Algorithm Design: Foundations, Analysis, and Internet Examples (англ.). — John Wiley & Sons, 2002. — P. 241–243.
• Hagerup, Torben. Towards optimal parallel bucket sorting (англ.) // Information and Computation. — 1987. — Vol. 75, no. 1. — P. 39–51. — doi:10.1016/0890-5401(87)90062-9.
• Han, Yijie. Deterministic sorting in O(n log log n) time and linear space (англ.) // Journal of Algorithms. Cognition, Informatics and Logic. — 2004. — Vol. 50, no. 1. — P. 96–105. — doi:10.1016/j.jalgor.2003.09.001.
• Han, Yijie, Thorup, M. Symposium on Foundations of Computer Science (англ.). — 2002. — P. 135–144. — doi:10.1109/SFCS.2002.1181890.
• Kirkpatrick, David, Reisch, Stefan. Upper bounds for sorting integers on random access machines (англ.) // Theoretical Computer Science. — 1984. — Vol. 28, no. 3. — P. 263–276. — doi:10.1016/0304-3975(83)90023-3.
• McIlroy, Peter M., Bostic, Keith, McIlroy, M. Douglas. Engineering Radix Sort (англ.) // Computing Systems. — 1993. — Vol. 6, no. 1. — P. 5–27.
• Pedersen, Morten Nicolaj. A study of the practical significance of word RAM algorithms for internal integer sorting (англ.). — Department of Computer Science, University of Copenhagen, Denmark, 1999. Архивировано 16 марта 2012 года.
• Rahman, Naila, Raman, Rajeev. Algorithm Engineering, 2nd International Workshop, WAE '92, Saarbrücken, Germany, August 20–22, 1998, Proceedings (англ.). — Max Planck Institute for Computer Science, 1998. — P. 193–203.
• Reif, John H. Symposium on Foundations of Computer Science (англ.). — 1985. — P. 496–504. — doi:10.1109/SFCS.1985.9.
• Thorup, Mikkel. Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise Boolean operations (англ.) // Journal of Algorithms. — 2002. — Vol. 42, no. 2. — P. 205–230. — doi:10.1006/jagm.2002.1211.
• Thorup, Mikkel. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003) (англ.). — ACM, 2003. — P. 699–707.
• Thorup, Mikkel. Equivalence between priority queues and sorting (англ.) // Journal of the ACM. — 2007. — Vol. 54, no. 6. — doi:10.1145/1314690.1314692.
• Willard, Dan E. Log-logarithmic worst-case range queries are possible in space Θ(N) (англ.) // Information Processing Letters. — 1983. — Vol. 17, no. 2. — P. 81–84. — doi:10.1016/0020-0190(83)90075-3.