| Peer-Reviewed

Performance Analysis of Sorting Process with Different Sampling Strategies

Received: 14 November 2018     Accepted: 13 December 2018     Published: 16 January 2019
Views:       Downloads:
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.

Published in Science Journal of Applied Mathematics and Statistics (Volume 6, Issue 6)
DOI 10.11648/j.sjams.20180606.11
Page(s) 148-160
Creative Commons

This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.

Copyright

Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Sorting, Algoritms, Divide and Conquer, Performance, Stochastic Process, Convergence Cadlag Functions, Asymptotics, Skorodhod Metric

References
[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.
Cite This Article
  • APA Style

    Mahmoud Ragab. (2019). Performance Analysis of Sorting Process with Different Sampling Strategies. Science Journal of Applied Mathematics and Statistics, 6(6), 148-160. https://doi.org/10.11648/j.sjams.20180606.11

    Copy | Download

    ACS Style

    Mahmoud Ragab. Performance Analysis of Sorting Process with Different Sampling Strategies. Sci. J. Appl. Math. Stat. 2019, 6(6), 148-160. doi: 10.11648/j.sjams.20180606.11

    Copy | Download

    AMA Style

    Mahmoud Ragab. Performance Analysis of Sorting Process with Different Sampling Strategies. Sci J Appl Math Stat. 2019;6(6):148-160. doi: 10.11648/j.sjams.20180606.11

    Copy | Download

  • @article{10.11648/j.sjams.20180606.11,
      author = {Mahmoud Ragab},
      title = {Performance Analysis of Sorting Process with Different Sampling Strategies},
      journal = {Science Journal of Applied Mathematics and Statistics},
      volume = {6},
      number = {6},
      pages = {148-160},
      doi = {10.11648/j.sjams.20180606.11},
      url = {https://doi.org/10.11648/j.sjams.20180606.11},
      eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.sjams.20180606.11},
      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.},
     year = {2019}
    }
    

    Copy | Download

  • TY  - JOUR
    T1  - Performance Analysis of Sorting Process with Different Sampling Strategies
    AU  - Mahmoud Ragab
    Y1  - 2019/01/16
    PY  - 2019
    N1  - https://doi.org/10.11648/j.sjams.20180606.11
    DO  - 10.11648/j.sjams.20180606.11
    T2  - Science Journal of Applied Mathematics and Statistics
    JF  - Science Journal of Applied Mathematics and Statistics
    JO  - Science Journal of Applied Mathematics and Statistics
    SP  - 148
    EP  - 160
    PB  - Science Publishing Group
    SN  - 2376-9513
    UR  - https://doi.org/10.11648/j.sjams.20180606.11
    AB  - 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.
    VL  - 6
    IS  - 6
    ER  - 

    Copy | Download

Author Information
  • Mathematics Department, Faculty of Science, Al-Azhar University, Cairo, Egypt

  • Sections