Performance Analysis of Sorting Process with Different Sampling Strategies

摘要

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.