|
| | | | |
| | | |
| Stat |
Members: 3665
Articles: 2'599'751
Articles rated: 2609
25 January 2025 |
|
| | | | |
|
Article overview
| |
|
|
Optimization Perspectives on Shellsort | | Oscar Skean
; Richard Ehrenborg
; Jerzy W. Jaromczyk
; | | Date: |
1 Jan 2023 | | Abstract: | Shellsort is a sorting method that is attractive due to its simplicity, yet
it takes effort to analyze its efficiency. The heart of the algorithm is the
gap sequence chosen a priori and used during sorting. The selection of this gap
sequence affects the efficiency of Shellsort, and thus drives both its
theoretical and experimental analysis. We contribute to Shellsort by
identifying efficient gap sequences based on new parameterized functions.
Specifically, a parameter grid-search identifies optimal parameters for
different input sizes for sorting by observing minimal overhead in three
categories: number of comparisons, number of exchanges, and running time. We
report that our method finds sequences that outperform state-of-the-art gap
sequences concerning the number of comparisons for chosen small array sizes.
Additionally, our function-based sequences outperform the running time of the
Tokuda sequence for chosen large array sizes. However, no substantial
improvements were observed when minimizing the number of exchanges. | | Source: | arXiv, 2301.00316 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER