Explore –Journal of Research
Peer Reviewed Journal
ISSN 2278–0297 (Print)
ISSN 2278–6414 (Online)
Vol. XIV No. 2, 2022
© Patna Women’s College, Patna, India
A Comparative Analysis of Sorting Algorithms under Discrete Uniform Distribution
Priyadarshini
Received : April 2022
Accepted : May 2022
Corresponding Author : Priyadarshini
Abstract : Sorting can be viewed as one of the fundamental aspects of computer applications. The efficiency of a sorting algorithm is a major issue when the amount of data to be sorted is large. Different sorting algorithms are analyzed based on time complexity and space complexity to select the efficient one based on their execution time for varying input sizes. In the case of sorting algorithms, when the array elements to be sorted are randomly generated from some probability distribution; then the true ability of an algorithm can be judged only when it is supported by the study of parametric complexity analysis which includes the study of the behaviour of running times as a function of parameters of the input distribution. To select a particular sorting algorithm from among a set of several algorithms, the behaviour of the parameters of the input distribution plays an important role and it can’t be ignored as far as the efficiency of the algorithm is concerned. In this paper, discrete uniform distribution is chosen for the study.
Three sorting algorithms, having similar average-case complexity O (N log N), quick sort, heap sort and merge sort have been chosen here for statistical comparative study of their parametric complexity. The purpose of the study is to investigate the effect of the parameter of the discrete uniform distribution on the sorting time of the three sorting algorithms under study. While working with several algorithms, one way to judge the best algorithm is to find the execution time T(n), as a function of N(input size) and examine the run time complexity using big O notation. However, sometimes it is difficult to find the exact form of the function and it becomes difficult to predict the complexity/ efficiency of an algorithm. Further, it has been tried to find the best sorting algorithm by performing a variance-based analysis of the sorting algorithms.
Keywords : Sorting, parametric complexity, discrete uniform distribution, variance, the average case, worst case
Priyadarshini
Assistant Professor, Patna Women’s College, P.U.
Email-id : singh.priyadarshini80@gmail.com
