A heuristic approximation of the worst case of Shellsort |
| |
Authors: | Hannu Erkiö |
| |
Institution: | (1) Department of Computer Science, University of Helsinki, Tukholmankatu 2, SF-00250 Helsinki 25, Finland |
| |
Abstract: | A heuristic algorithm is presented to construct permutations which require as many moves in sorting by Shellsort as possible. The approximations obtained are compared with those found by other known methods. Experiments were performed with up ton=2047 elements to be sorted, and the results show the distinct superiority of the heuristic approximations. The actual times needed by Shellsort to sort the worst permutations achieved were determined and compared with the corresponding times of Shellsort in the average case, as well as with the times of quicksort and heapsort in their worst cases. |
| |
Keywords: | Shellsort worst case analysis internal sorting heuristic approximation combinatorial optimization |
本文献已被 SpringerLink 等数据库收录! |
|