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

Lists

Download

BitIdx-Sort-2.pdf (821kB)

Restricted to Repository staff only

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.

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)
URI	https://reading-clone.eprints-hosting.org/id/eprint/39935
Item Type	Conference or Workshop Item
Refereed	Yes
Divisions	Science
Uncontrolled Keywords	sorting algorithm, permutations, linear complexity, bit-array index, counting leading zeros, counting trailing zeros.
Download/View statistics	View download statistics for this item

Deposit Details

Date Deposited:	21 Apr 2015 15:21	Date item deposited into CentAUR
Last Modified:	10 Jul 2021 22:49	Date item last modified

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

Search Google Scholar