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 95
- Downloads 0
Developing Predictive Models using Typical Machine Learning and Computational Techniques
This study investigates the accuracy of developing predictive models using machine learning techniques. The machine learning techniques considered in this study include artificial neural network (ANN) and Kalman filter a...
Variance Components of Models of Sudoku Square Design
This study aimed at obtaining variance component estimators for all effects of Sudoku square models. The analysis of variance (ANOVA) method was used for the derivation of the variance components for the four Sudoku mode...
Prediction of Skin Disease using Decision Tree and Artificial Neural Network (ANN)
Skin diseases are common diseases that exist between the children and adults in the society. The issue of finding and proffering a better skin disease predictive model in the health care system has been identified to be...
Framework for a Genetic-Neuro-Fuzzy Inferential System for Diagnosis of Diabetes Mellitus
One of the most dangerous diseases in the modern society is diabetes mellitus and it is not only a medical problem but also a socio-economy. Artificial Intelligence techniques have been successfully employed in diabetes...
Password Authentication Scheme with Secured Login Interface
This paper presents a novel solution to the age long problem of password security at input level. In our solution, each of the various characters from which a password could be composed is encoded with a random single di...