정수 정렬

컴퓨터 과학에서 정수 정렬(Integer sorting)은 정수 키들에 따라 데이터 값을 수집하는 정렬 알고리즘 문제이다. 정수 정렬을 위해 설계된 알고리즘들은 키가 부동소수점 수, 유리수, 텍스트 문자열인 정렬 문제들에도 적용할 수 있다. 키들에 대한 정수 산술을 수행할 수 있기 때문에 컴퓨팅 모델에서 허용되는 작업의 세부 내용에 따라, 또 정렬되는 정수가 얼마나 큰지에 따라 많은 경우에서 비교 정렬 알고리즘에 비해 정수 정렬 알고리즘을 더 빠르게 수행할 수 있다.

피존홀 정렬, 계수 정렬, 기수 정렬을 포함한 정수 정렬 알고리즘들이 널리 사용되고 있으며 실용적이다.

참고 자료

• Han, Yijie; Thorup, M. (2002), 〈Integer sorting in O(n√log log n) expected time and linear space〉, 《Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002)》, IEEE Computer Society, 135–144쪽, doi:10.1109/SFCS.2002.1181890  .