The week's pick
Reseach Article
Article:Randomized Signature Sort: Implementation & Performance Analysis
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 23 - Number 6 |
| Year of Publication: 2011 |
| Authors: Tamana Pathak, Dr. Deepak Garg |
10.5120/2895-3787
|
Tamana Pathak, Dr. Deepak Garg . Article:Randomized Signature Sort: Implementation & Performance Analysis. International Journal of Computer Applications. 23, 6 ( June 2011), 1-5. DOI=10.5120/2895-3787
Abstract
Recently the lower bound for integer sorting has considerably improved and achieved with comparison sorting O(n log n) to O (n√(loglogn )) [1] for a deterministic algorithms or to O(n) for a radix sort algorithm in space that depends only on the number of input integers. Andersson et al. [2] presented signature sort in the expected linear time and space which gives very bad performance than randomized quick sort. We earlier presented in [14] that performance of signature sort can be enhanced using hashing and bitwise operators. This paper gives the implementation of that idea and later we have compared the performance of algorithm with existing randomized signature sort and randomized quick Sort.
References
- Yijie Han and Mikkel Thorup. Integer sorting in O(n√(loglogn ) ) expected time and linear space. In IEEE Symp. on Foundations of Computer Science, volume 43, 2002.
- Andersson, Hagerup, Nilsson, and Raman. Sorting in linear time? In STOC: ACM Symposium on Theory of Computing (STOC), 1995.
- D. Kirkpatrick and S. Reisch. Upper bounds for sorting integers on random access machines. 1984.
- M. L. Fredman and D. E. Willard. Surpassing the information theoretic bound with fusion trees.1993. Announced at STOC’90.
- W. Paul and J. Simon. Decision trees and random access machines. In Proc. Symp. ¨uber Logik and Algoritmik, 1980.
- L. J. Comrie. The hollerith and powers tabulating machines.Trans. Office Machinary Users’ Assoc., Ltd, 1929-30.
- A. I. Dumey. Indexing for rapid random access memory systems. Computers and Automation, 1956.
- Mikkel Thorup. Randomized sorting in O (n log log n) time and linear space using addition, shift, & bit-wise boolean operations.
- Y. Han: Deterministic Sorting in O (n log log n) Time and Linear Space, J. Algorithms 50(1): 2004. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, Second Edition, The MIT Press and McGraw-Hill Book Company2001.
- S. Cook and R. Reckhow. Time-bounded random access machines. J. Comp. Syst. Sc., 10(2):1973. M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen, A reliable randomized algorithm for the closest- pair problem, J. Algorithms 25 (1997).
- B. Vandiver, A.Rolfe, Exploiting sleight-of model to achieve super-luminal sorting: 2003
- T. Pathak, D. Garg, Improving performance of Randomized Signature Sort using hashing and Bitwise operators, JGRCS Vol 2 No 3, 2011.
Index Terms
Keywords