Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

Lists

Tools

Curi-Quintal, L. F., Cadenas Medina, J. and Megson, G. M. (2013) Bit-index sort: a fast non-comparison integer sorting algorithm for permutations. In: International Conference on Technological Advances in Electrical, Electronics and Computer Engineering (TAEECE), 2013, 9-11 May 2013, Konya, pp. 83-87.

Text
· Restricted to Repository staff only
· The Copyright of this document has not been checked yet. This may affect its availability.
821kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

Official URL: http://dx.doi.org/10.1109/TAEECE.2013.6557200

Abstract/Summary

This paper describes a fast integer sorting algorithm, herein referred as Bit-index sort, which is a non-comparison sorting algorithm for partial per-mutations, with linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers supported by machine hardware to retrieve the ordered output sequence. Results show that Bit-index sort outperforms in execution time to quicksort and counting sort algorithms. A parallel approach for Bit-index sort using two simultaneous threads is included, which obtains speedups up to 1.6.

Item Type:	Conference or Workshop Item (Paper)
Refereed:	Yes
Divisions:	Science
ID Code:	39935
Uncontrolled Keywords:	sorting algorithm, permutations, linear complexity, bit-array index, counting leading zeros, counting trailing zeros.

Deposit Details

References

[1] T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. Cambridge, Mass. U.S.A.: MIT Press, 1990. [2] C. A. R. Hoare, “Quicksort,” The Computer Journal, vol. 5, no. 1, pp. 10–16, 1962. [3] S. Carlsson, “Average-case results on heapsort,” BIT Numerical Mathematics, vol. 27, no. 1, pp. 2–17, 1987. [4] D. Knuth, The Art of Computer Programming V3: Sorting and Searching, Second Ed. Reading Mass. USA: Addison-Wesley, 1998. [5] I. J. Davis, “A Fast Radix Sort,” The Computer Journal, vol. 35, no. 6, pp. 636–642, Dec. 1992. [6] R. Merris, Combinatorics, Second Edi. Hoboken, NJ, USA: John Wiley, 2003. [7] D. Babu and R. Shankar, “Array-indexed sorting algorithm for natural numbers,” in 2011 IEEE 3rd International Conference on Communication Software and Networks, 2011, pp. 606–609. [8] S. Bao, Y. Xu, D. Zheng, and Z. Zhao, “Novel Sorting Algorithm Based on Guessing Function,” in 2006 IEEE International Symposium on Signal Processing and Information Technology, 2006, pp. 411–414. [9] Intel Corp., Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2: Instruction Set Reference, Order Numb. 2013, pp. 3–74, 3–76. [10] I. Corp., PowerPC User Instruction Set Architecture Book 1 Version 2.02. IBM Corp., 2003, p. 70. [11] A. Inc., AMD64 Architecture Programmer’s Manual Volume 3: General Purpose and System Instructions, 24594 Rev. AMD Inc., 2012, p. 210,309. [12] A. Limited, ARM Developer Suite Version 1.2 Assembler Guide, Release 1. ARM Limited, 2001, pp. 4–38. [13] F. S. F. Inc., “Using the GNU compiler collection. 5.46 Other built-in functions provided by GCC,” 2005. [Online]. Available: http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Other-Builtins.html. [Accessed: 15-Feb-2013]. [14] Microsoft, “MSDN Library. Visual Studio 2012. Compiler Intrinsics,” __lzcnt16, __lzcnt, __lzcnt64, 2013. [Online]. Available: http://msdn.microsoft.com/en-us/library/bb384809(v=vs.100).aspx. [Accessed: 15-Feb-2013]. [15] Intel Corp., Intel C++ Compiler for Linux. Intrinsics Reference, 312482nd–001 ed. Intel Corp., 2006, p. 21. [16] N. Corp., CUDA C Programming Guide, PG-02829–0 ed. NVIDIA Corp., 2012, p. 79. [17] The Open Group Base, “qsort(),” IEEE Std 1003.1 Issue 6, 2004. [Online]. Available: http://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.html. [Accessed: 25-Nov-2012]. [18] O. A. R. Board, OpenMP Aplication Program Interface, Version 3. OpenMP Architecture Review Board, 2011, p. 48.

University Staff: Request a correction | Centaur Editors: Update this record

University of Reading

CentAUR: Central Archive at the University of Reading

Accessibility navigation

Bit-index sort: a fast non-comparison integer sorting algorithm for permutations

Abstract/Summary

Page navigation

See also

Footer navigation