Beta
382874

Complexity analysis and performance of double hashing sort algorithm

Article

Last updated: 21 Dec 2024

Subjects

-

Tags

-

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.

DOI

10.1186/s42787-019-0004-2

Keywords

Sorting, Quick sort, Counting sort, Performance of algorithm, Complexity analysis

Authors

First Name

Hazem

Last Name

Bahig

MiddleName

M.

Affiliation

Computer Science Division, Department of Mathematics, Faculty of Science, Ain Shams University, Cairo 11566, Egypt, College of Computer Science and Engineering, Hail University, Hail, Kingdom of Saudi Arabi

Email

hazem.m.bahig@gmail.com

City

-

Orcid

-

Volume

27

Article Issue

1

Related Issue

50652

Issue Date

2019-12-01

Receive Date

2024-09-30

Publish Date

2019-12-01

Page Start

1

Page End

12

Print ISSN

1110-256X

Online ISSN

2090-9128

Link

https://joems.journals.ekb.eg/article_382874.html

Detail API

https://joems.journals.ekb.eg/service?article_code=382874

Order

3

Publication Type

Journal

Publication Title

Journal of the Egyptian Mathematical Society

Publication Link

https://joems.journals.ekb.eg/

MainTitle

Complexity analysis and performance of double hashing sort algorithm

Details

Type

Article

Created At

21 Dec 2024