Parameterized Complexity on a New Sorting Algorithm: A Study in Simulation<br />
Journal Title: Annals. Computer Science Series - Year 2009, Vol 7, Issue 2
Abstract
Sundararajan and Chakraborty (2007) introduced a new sorting algorithm by modifying the fast and popular Quick sort and removing the interchanges. In a subsequent empirical study, Sourabh, Sundararajan and Chakraborty (2007) demonstrated that this algorithm sorts inputs from certain probability distributions faster than others and the authors made a list of some standard probability distributions in decreasing order of speed, namely, Continuous uniform, Discrete uniform, Binomial, Negative Binomial, Poisson, Geometric, Exponential, Standard Normal. It is clear from this interesting second study that the algorithm is sensitive to input probability distribution. Based on these pervious findings, in the present paper we are motivated to do some further study on this sorting algorithm through simulation and determine the appropriate empirical model which explains its average sorting time with special emphasis on parameterized complexity.
Authors and Affiliations
Prashant KUMAR , Anchala KUMARI, Soubhik CHAKRABORTY
Keywords
Related Articles
- EP ID EP123964
- DOI -
- Views 93
- Downloads 0
Technical Methods and Algorithms for Developing Efficient Optical Character Recognition System: An Overview
Machine recognition problem of printed documents in Optical Character Recognition has been the target of research in the area of pattern recognition. Study in this aspect has been controlled by a need to join the natural...
Technique detection software for Sparse Matrices
Sparse storage formats are techniques for storing and processing the sparse matrix data efficiently. The performance of these storage formats depend upon the distribution of non-zeros, within the matrix in different dime...
Analysis of the Electrocardiogram by Means of Characteristics of the Disproportionality of Numerical Functions
Electrocardiography: this is a method of recording the potential difference between two points in the electric field of the heart during its excitation. The modern technology allow you to record ECG on a long time interv...
Are Subsequences of Decimal Digits of PI Random?
A lot has been done on the randomness of the decimal expansion of Pi with extensive tests of randomness that are used to distinguish good from not-so-good random number generators when applied to the decimal digits of Pi...
Quality certification of the medical information systems - An overview -
Resistance to change is something specifically human, being an easy thing to understand, but it has to be overcome now, and not as it happens, after generations. The certification process currently exists in many areas....