Archive
Special Issues

Volume 6, Issue 6, December 2018, Page: 148-160
Performance Analysis of Sorting Process with Different Sampling Strategies
Mahmoud Ragab, Mathematics Department, Faculty of Science, Al-Azhar University, Cairo, Egypt
Received: Nov. 14, 2018;       Accepted: Dec. 13, 2018;       Published: Jan. 16, 2019
Abstract
Sorting data is one of the most important problems that play an important rule in many applications in operations research, computer science and many other applications. Many sorting algorithms are well studied but the problem is not to find a way or algorithm to sort elements, but to find an efficiently way to sort elements and do the job. The output is a stream of data in time and it is a sorted data array. We are interested in this flow of data to estaplish a smart technique to sort elements as well as efficient complexity. For the performance of such algorithms, there has been little research on their stochastic behavior and mathematical properties such existance and convergence properties. In this paper we study the mathematical behavior of some different versions sorting algorithms in the case when the size of the input is very large. This work also discuss the corresponding running time using some different strategies in terms of number of comparisons and swaps. Here, we use a nice approach to show the existence of partial sorting process via the weighted branching process. This approach was inspired by the methods used for the analysis of Quickselect and Quichsort in the standard cases, where fixed point equations on the Cadlag space were considered for the first time.
Keywords
Sorting, Algoritms, Divide and Conquer, Performance, Stochastic Process, Convergence Cadlag Functions, Asymptotics, Skorodhod Metric
Mahmoud Ragab, Performance Analysis of Sorting Process with Different Sampling Strategies, Science Journal of Applied Mathematics and Statistics. Vol. 6, No. 6, 2018, pp. 148-160. doi: 10.11648/j.sjams.20180606.11
Reference
[1]
Daniel H. Greene and Donald E. Knuth. Mathematics for the analysis of algorithms. Modern Birkhäuser Classics. Birkhäuser Boston Inc., Boston, MA, 2008. Reprint of the third (1990) edition.
[2]
C. A. R. Hoare. Quicksort. Comput. J., 5:10–15, 1962.
[3]
Mahmoud Ragab, Beih El-Sayed El-Desouky, and Nora Nader. Analysis of the multi-pivot quicksort process. Open Journal of Modelling and Simulation, 5(01):47–58, 2017.
[4]
U. Rösler. On the analysis of stochastic divide and conquer algorithms. Algorithmica, 29(1-2):238–261, 2001. Average-case analysis of algorithms (Princeton, NJ, 1998).
[5]
Mahmoud Ragab. Partial Quicksort and weighted branching processes. PhD thesis, Kiel, Christian-Albrechts-Universität, Diss., 2011, 2011.
[6]
Mahmoud Ragab. Running time Analysis of Sorting Algorithm via an Asymptotic Distribution. International Refereed Journal of Engineering and Science (IRJES), 6(8):55–69, 2017.
[7]
Uwe Rösler. The weighted branching process. Dynamics of complex and irregular systems (Bielefeld, 1991), pages 154–165, 1993.
[8]
U. Roesler and L. Rueschendorf. The contraction method for recursive algorithms. Algorithmica, 29(1-2):3–33, 2001. Average-case analysis of algorithms (Princeton, NJ, 1998).
[9]
Ralph Neininger and Ludger Rüschendorf. Analysis of algorithms by the contraction method: additive and max-recursive sequences. In Interacting stochastic systems, pages 435–450. Springer, Berlin, 2005.
[10]
Diether Knof and Uwe Roesler. The analysis of find or perpetuities on cadlag functions. Discrete Mathematics and Theoretical Computer Science, 2010.
[11]
Mahmoud Ragab and Uwe Roesler. The quicksort process. Stochastic processes and their Applications, 124(2):1036–1054, 2014.
[12]
Conrado Martnez and Uwe Roesler. Partial quicksort and quickpartitionsort. DMTCS Proceedings, (01):505–512, 2010.
[13]
Mahmoud Ragab. On the quicksort algorithm and its related process. Journal of Mathematical Modeling and Operations Research, 01(01):13–30, 2015.
[14]
Mahmoud Ragab, Beih El-Sayed El-Desouky, and Nora Nader. On the convergence of the dual-pivot quicksort process. Open Journal of Modelling and Simulation, 4(01):1–15, 2016.