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 120
- Downloads 0
Iterative Methods for Systems’ Solving - a C# approach
This work wishes to support various mathematical issues concerning the iterative methods with the help of new programming languages. We consider a way to show how problems in math have an answer by using different academ...
Homogenous Ensembles of Data Mining Algorithms in Predicting Liver Disease
Application of data mining algorithms to medical fields have been of interest as it helps patients get access to a better and faster healthcare. In this study, the effect of homogenous ensemble methods of bagging and boo...
PIFA: Designing a Personalized Information Filtering Algorithm for Knowledge Management Systems
A study on the concept of “personalized information filtering” system was carried out. Natural Language Processing (NLP) was used to tag the words, and metrics such as TF-IDF was used to weigh each term in the document....
Modelling of Enugu State Monthly Rainfall using Box and Jenkins Methodology
The paper examined the rainfall distribution of Enugu state in Nigeria. Box-Jenkins methodology was used to build ARIMA model to analyze data and forecast for the period of 15 years, from January, 2002 to December, 2016...
Network Traffic and Utilization: Reliability of Network Analyzer Development with Independent Data, OPNET Simulation Tool and Real Network
This paper presents a complete network analyzer development for heterogeneous services in campus environment. The purpose of this study is to define the accuracy of network analyzer development with independent data, rea...