Sorting in one round |
| |
Authors: | Béla Bollobás Moshe Rosenfeld |
| |
Institution: | (1) Cambridge University, Cambridge, England;(2) Ben Gurion University of the Negev, Beer Sheva, Israel |
| |
Abstract: | Given an ordered set ofn elements whose order is not known to us, it is shown that by making slightly more thancn
3/2 simultaneous comparison almost all comparisons can be deduced by direct implications. It is also shown that this result is
essentially best possible, and that ifn is large, almost any choice ofcn
3/2 comparisons will yield almost all comparisons by direct implications. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|