The week's pick
Random Articles
Reseach Article
Implementation and Performance Analysis of Exponential Tree Sorting
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 24 - Number 3 |
| Year of Publication: 2011 |
| Authors: Ajit Singh, Dr. Deepak Garg |
10.5120/2929-3876
|
Ajit Singh, Dr. Deepak Garg . Implementation and Performance Analysis of Exponential Tree Sorting. International Journal of Computer Applications. 24, 3 ( June 2011), 34-38. DOI=10.5120/2929-3876
Abstract
The traditional algorithm for sorting gives a bound of O(n log n) expected time without randomization and O(n) with randomization. Recent researches have optimized lower bound for deterministic algorithms for integer sorting [1-3]. Andersson has given the idea of Exponential tree which can be used for sorting [4]. Andersson, Hagerup, Nilson and Raman have given an algorithm which sorts n integers in O(n log log n) expected time but uses O(mᵋ) space [4, 5]. Andersson has given improved algorithm which sort n integers in O(n log log n) expected time and linear space but uses randomization [2, 4]. Yijie Han has improved further to sort n integers in O(n log log n) expected time and linear space but passes integers in a batch i.e. all integers at a time [6]. These algorithms are very complex to implement. In this paper we discussed a way to implement the exponential tree sorting and later compare results with traditional sorting technique.
References
- M. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen, A reliable randomized algorithm for the closest-pair problem, J. Algorithms 25, 1997.
- M. Thorup, Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise boolean operations, in: Proc. 8th ACM–SIAM Symposium on Discrete Algorithms (SODA’97), 1997.
- Y. Han, M. Thorup, Sorting integers in O(n √(loglogn )) expected time and linear space, IEEE Symposium on Foundations of Computer Science (FOCS’02), 2002.
- A. Andersson, T. Hagerup, S. Nilsson, R. Raman, Sorting in linear time?, Symposium on Theory of Computing, 1995.
- Y. Han, X. Shen, Conservative algorithms for parallel and sequential integer sorting, International Computing and Combinatorics Conference, 1995.
- Y. Han, Deterministic sorting in O(n log log n) time and linear space, 34th STOC, 2002.
- P. van Emde Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue, Math. Syst. Theory 10, 1977.
- A. Andersson, Fast deterministic sorting and searching in linear space, IEEE Symposium on Foundations of Computer Science, 1996.
- Y. Han, Improved fast integer sorting in linear space, Inform. and Comput., 2001.
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, Second Edition,The MIT Press and McGraw-Hill Book Company, 2001.
- S. Albers, T. Hagerup, Improved parallel integer sorting without concurrent writing, Inform. and Comput., 1997.
- M.L. Fredman, D.E. Willard, Surpassing the information theoretic bound with fusion trees, J. Comput. System Sci., 1994.
- T. Hagerup, H. Shen, Improved nonconservative sequential and parallel integer sorting, Inform. Process. Lett., 1990.
- D. Kirkpatrick, S. Reisch, Upper bounds for sorting integers on random access machines, Theoret. Comput. Sci., 1984.
- R. Raman, Priority queues: small, monotone and trans-dichotomous, European Symp. on Algorithms, 1996.
- M. Thorup, Fast deterministic sorting and priority queues in linear space, ACM–SIAM Symp. on Discrete Algorithms (SODA’98), 1998.
Index Terms
Keywords