Stack sort: a new approach with sorting network and a buffer
DOI:
https://doi.org/10.56294/sctconf2024898Keywords:
Single Stack, Sorting Network, Buffer, Sort, ComplexityAbstract
Knuth introduced the problem of stack sorting. Stack sorting was implemented by t stacks in series. In this paper, we propose a new dimension to stack sorting problem by introducing a stack with sorting network and a petty buffer. Instead of using t stacks in series, it helps to improve the performance by avoiding shuffles the stack. The basic idea behind in this paper is to perform a stack sorting with a single stack, and to achieve greater performance. In this novel approach, 2 bit buffer is compared to stack and insert the element into stack in order to avoid multiple stack. The result shows the time complexity of the proposed algorithm is O (n)
References
1. Tarjan R. Sorting using networks of queues and stacks. Journal of the ACM (JACM). 1972 Apr 1; 19(2): 341-346.
2. Unger W. On the k-colouring of circle-graphs. In Annual Symposium on Theoretical Aspects of Computer Science. Berlin, Heidelberg: Springer Berlin Heidelberg. 1988 Feb 11: 61-72.
3. Bóna M. A survey of stack-sorting disciplines. the electronic journal of combinatorics. 2002: A1. https://doi.org/10.37236/1693
4. Knuth DE. Fundamental Algorithms, vol. 1 of The Art of Computer Programming, section 1.2. Reading, Massachusetts: Addison-Wesley. 1973 Jan; 10: 10-19.
5. Zeilberger D. A proof of Julian West's conjecture that the number of two-stack sortable permutations of length n is 2 (3n)! / ((n+ 1) ! (2n+ 1)!). Discrete Mathematics. 1992 May 18; 102(1): 85-93.
6. LIM, C. H. Brief Introduction on Stack Sorting. https://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Lim.pdf
7. König FG, Lübbecke ME. Sorting with complete networks of stacks. In International Symposium on Algorithms and Computation. Berlin, Heidelberg: Springer Berlin Heidelberg. 2008 Dec 15: 895-906.
8. Smith R. Comparing algorithms for sorting with t stacks in series. Annals of Combinatorics. 2004 May; 8(1): 113-121.
9. Atkinson MD, Murphy MM, Ruškuc N. Sorting with two ordered stacks in series. Theoretical Computer Science. 2002 Oct 23; 289(1): 205-223.
10. König FG, Lübbecke M, Möhring R, Schäfer G, Spenke I. Solutions to real-world instances of PSPACE-complete stacking. In European Symposium on Algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg. 2007 Oct 8, pp. 729-740.
11. Marc P. The Bi-Stack Sorting Problem. Master’s thesis, Department of Data Science and Knowledge Engineering, Maastricht University. 2019.
12. Mihalák M, Pont M. On Sorting with a Network of Two Stacks. In19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019) 2019.
13. Qian M, Wang X. Queue and stack sorting algorithm optimization and performance analysis. In AIP Conference Proceedings, AIP Publishing. 2018 Apr 18, 1955(1).
14. Pudwell L, Smith R. Two-stack-sorting with pop stacks. Australasian Journal of Combinatorics. 2019; 74(1): 179–195.
15. Cerbai G, Cioni L, Ferrari L. Stack Sorting with Increasing and Decreasing Stacks. The Electronic Journal of Combinatorics. 2020; 27(1): 1–17.
16. Cerbai G, Claesson A, Ferrari L. Stack sorting with restricted stacks. Journal of Combinatorial Theory, Series A. 2020 Jul 1; 173: 105230. https://doi.org/10.1016/j.jcta.2020.105230
17. Colin Defant, Kai Zheng. Stack-Sorting_with_Consecutive-Pattern-Avoiding_Stacks. 2020; August 2020. https://arxiv.org/pdf/2008.12297.pdf
18. Berlow K. Restricted stacks as functions. Discrete Mathematics. 2021 Nov 1; 344(11): 112571. https://doi.org/10.48550/arXiv.2008.01164
19. Felsner S, Pergel M. The Complexity of Sorting with Networks of Stacks and Queues. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. 2008. https://doi.org/10.1007/978-3-540-87744-8_35.
Published
Issue
Section
License
Copyright (c) 2024 S. Muthusundari, V. Devi , S. Sharath Kumar , D. Sudhish Reddy , Kannedari Uday Kiran , Pulimi Hanith Sai Kumar Reddy , Gosani Bhanu Sai Priya , Katragunta Yagna Priya (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
The article is distributed under the Creative Commons Attribution 4.0 License. Unless otherwise stated, associated published material is distributed under the same licence.
