Performance Analysis of Sorting Process with Different Sampling Strategies

Mahmoud Ragab

doi:doi:10.11648/j.sjams.20180606.11

| Peer-Reviewed

Performance Analysis of Sorting Process with Different Sampling Strategies

Mahmoud Ragab

Published in Science Journal of Applied Mathematics and Statistics (Volume 6, Issue 6)

Received: 14 November 2018 Accepted: 13 December 2018 Published: 16 January 2019

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

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

Plain Text BibTeX RIS

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

Mahmoud Ragab

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

Download PDF

Sections

Plain Text BibTeX RIS

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