Complexity analysis and performance of double hashing sort algorithm | ||
| Journal of the Egyptian Mathematical Society | ||
| Article 3, Volume 27, Issue 1, 2019, Pages 1-12 PDF (934.32 K) | ||
| DOI: 10.1186/s42787-019-0004-2 | ||
| Author | ||
| Hazem M. Bahig1, 2 | ||
| 1Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt | ||
| 2College of Computer Science and Engineering, Hail University, Hail, Kingdom of Saudi Arabi | ||
| Abstract | ||
| Sorting an array of n elements represents one of the leading problems in different fields of computer science such as databases, graphs, computational geometry, and bioinformatics. A large number of sorting algorithms have been proposed based on different strategies. Recently, a sequential algorithm, called double hashing sort (DHS) algorithm, has been shown to exceed the quick sort algorithm in performance by 10–25%. In this paper, we study this technique from the standpoints of complexity analysis and the algorithm’s practical performance. We propose a new complexity analysis for the DHS algorithm based on the relation between the size of the input and the domain of the input elements. Our results reveal that the previous complexity analysis was not accurate. We also show experimentally that the counting sort algorithm performs significantly better than the DHS algorithm. Our experimental studies are based on six benchmarks; the percentage of improvement was roughly 46% on the average for all cases studied. | ||
| Keywords | ||
| Sorting; Quick sort; Counting sort; Performance of algorithm; Complexity analysis | ||
|
Statistics Article View: 47 PDF Download: 25 |
||
