Juggling Versus Three-Way-Reversal Sequence Rotation Performance Across Four Data Types

J. A. Erho¹ , J. I. Consul² , B. R. Japheth³

Section:Research Paper, Product Type: Journal-Paper
Vol.7 , Issue.6 , pp.10-18, Dec-2019

CrossRef-DOI:   https://doi.org/10.26438/ijsrcse/v7i6.1018

Online published on Dec 31, 2019

Copyright © J. A. Erho, J. I. Consul, B. R. Japheth . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

574 Views    407 Downloads    103 Downloads

Abstract :
Systems analysts, designers, and programmers normally choose among candidate algorithms to develop applications. This choice is even more crucial when the application is life critical, memory and/or time bound, such as embedded real-time systems. One of such choice making is in two leading candidate, high performance, sequence rotation algorithms ‒ juggling versus three-way-reversal ‒ often required for in-place sorting. The problem is identifying the best performing one among them and whether changes of elements versus indexes weights, in the form of altered data types, would shifts the performance index. This paper is therefore focused on investigating the performances differences of these algorithms across data types in adequately long stretched sequence, using both theoretical and statistical analysis. The objective is to measure the efficiencies of the algorithms around the variability of elements versus indexes weights. Using Java to implement the algorithms, pool of 35,500 records of execution timing for each of the data types were generated. Out of this number, 355 randomly sampled records from every next 100 were collected. Two-way analysis of variance (ANOVA) was carried out using R statistical package. The results of the analysis indicated that theoretically, juggling rotation might perform better in terms of time utilization. But statistically, the hypothesis test strongly suggested the contrary. The implication is that, with this study, users are better informed of which algorithm to adopt in practice. Given the conflicting theoretical and statistical results, it becomes necessary to investigate further the experimental low performance of juggling rotation.

Key-Words / Index Term :
juggling rotation, sequence rotation, sequence reversal, array rotation, rotation algorithm

References :
[1] P. M. Reddy, Reson, "Embedded Systems", Resonance, Springer, Vol. 7, Issue 12, pp. 20–30 , 2002.
[2] A. R. Mahajan, M. S. Ali, "Optimization of memory system in Real-Time Embedded Systems", In the Proceedings of the 11th WSEAS International Conference on COMPUTERS, Agios Nikolaos, Crete Island, Greece, pp. 14-19, 2007.
[3] T. H Cormen., C. E. Lieserson, R. L. Rivest, S. Clifford, "Introduction to Algorithms", The MIT Press Cambridge, Massachusetts London, England, pp. 17, 2009.
[4] C. A. R. Hoare, "Quicksort", The Computer Journal, Vol. 5, Issue 1, pp. 10–16, 1962.
[5] B-C. Huang, M. A. Langston, "Practical In-Place Merging", Communications of the ACM, Vol. 31, Issue 3, pp. 348-352, 1988.
[6] X. Wang, Y. Wub, D. Zhua, "A New Variant of In-Place Sort Algorithm", In the International Workshop on Information and Electronics Engineering (IWIEE), Procedia Engineering, Vol. 29, (Special Issue), pp. 2274-2278, 2012.
[7] H. Mannila, E. Ukkonen, "A Simple Linear-Time Algorithm for In Situ Merging", Information Processing Letters, Vol. 18, Issue 4, pp. 203-208, 1984.
[8] A. A Stepanov., D. E. Rose, "From Mathematics to Generic Programming", Pearson Education, Inc., USA, pp. 204-215, 2015.
[9] C. A. Furia "Rotation of Sequences: Algorithms and Proofs", Logic in Computer Science, Cornell University, USA , pp. 6-22, 2015.
[10] C. Shene, "An Analysis of Two In-Place Array Rotation Algorithms", The Computer Journal Vol. 40, Issue 9, pp. 541-546, 1997.
[11] B-C. Huang, M. A. Langston, "Fast Stable Merging and Sorting in Constant Extra Space", The Computer Journal, Vol. 35, Issue 6, pp. 643-650, 1992.
[12] A. Symvonis, "Optimal Stable Merging" , The Computer Journal, Vol. 38, Issue 8, pp. 681–690, 1995.
[13] J. A. Erho, J. I. Consul, "Precise Evaluation of Execution Cost of Sequence Rotation by Three-Way-Reversals", International Journal of Applied Science Research, Vol. 2, Issue 5, pp. 99-104, 2019.
[14] K. Dudzinski, A. Dydek, "On A Stable Minimum Storage Merging Algorithm", Information Processing Letters, Vol. 12, Issue 1, pp. 5-8, 1981.
[15] P. Kim, A. Kutzner, "Ratio based stable in-place merging", In the Proceedings of 5th International Conference on Theory and Applications of Models of Computation (TAMC), LNCS, Springer, Berlin, Heidelberg, Vol. 4978, pp. 246-257, 2008.
[16] A. Symvonis, "Optimal Stable Merging", In the Proceedings of the Int. Conf. on Computing and Information, (Proc. ICCI) Vol. 94, pp. 124-143, 1994.
[17] D. E. Knuth, "The Art of Computer Programming", Addison-Wesley Longman, USA, (Vol. 2 / Seminumerieal Algorithms, 3nd Edn), pp. 333-373, 1998.
[18] A. Iliev, N. Kyurkchiev, A. Rahnev, "A New Improvement Euclidean Algorithm for Greatest Common Divisor. I", Neural, Parallel, and Scientific Computations, Vol. 26, Issue 3, pp. 355-362, 2018.
[19] G. H. Norton, "On the Asymptotic Analysis of the Euclidean Algorithm", Journal of Symbolic Computation, Vol. 10, Issue 1, pp. 53-58, 1990.
[20] O. Bagdasar "On Some Functions Involving the lcm and gcd of Integer Tuples", APPL. MATH. INFORM. AND MECH. Vol. 6, Issue 2, pp. 91-100, 2014.
[21] G. H. Hardy and E. M. Wright, "An Introduction to the Theory of Numbers", Oxford University Press, London, (4th Edn), pp. 48-49, 1979
[22] A. A Stepanov., P. McJones, "Elements of Programming." Pearson Education, Inc., United States of America, pp. 73-78, 2014.
[23] C. A. Elliott, A. W. Woodward. "Statistical Analysis, Quick Reference Guidebook with SPSS Examples", SAGE publications, California, United States of America, pp. 166-175, 2007
[24] R Core Team , "R: A language and environment for statistical computing." R foundation for statistical computing, Vienna, Austria, 2014.