On the distribution of comparisons in sorting algorithms |
| |
Authors: | Dana Richards Pravin Vaidya |
| |
Institution: | (1) Dept. of Computer Science, University of Virginia, 22903 Charlottesville, VA, USA;(2) Dept. of Computer Science, University of Illinois, 61801 Urbana, IL, USA;(3) Present address: AT&T Bell Laboratories, 07974 Murray Hill, NJ |
| |
Abstract: | We considered the following natural conjecture: For every sorting algorithm every key will be involved in(logn) comparisons for some input. We show that this is true for most of the keys and prove matching upper and lower bounds. Every sorting algorithm for some input will involven–n
/2+1 keys in at leastlog2
n comparisons,>0. Further, there exists a sorting algorithm that will for every input involve at mostn–n
/c
keys in greater thanlog2
n comparisons, wherec is a constant and>0. The conjecture is shown to hold for natural algorithms from the literature. |
| |
Keywords: | F 2 2 |
本文献已被 SpringerLink 等数据库收录! |
|