C. Greg Plaxton Torsten Suel Department of Computer Science University of...  @ NUS Home/Search
Context Related
| poly.edu/~suel/papers/shell2.ps Cached: PS.gz PS PDF Image Update Help From: poly.edu/~suel/papers/papers (more) (Enter author homepages) |
Rate this article:      (best)Comment on this article |
Abstract: We show lower bounds on the worst-case complexity of Shellsort. In particular, ) lower bound for the size of Shellsort sorting networks, for arbitrary increment sequences. We also show an identical lower bound for the running time of Shellsort algorithms, again for arbitrary increment sequences. Our lower bounds establish an almost tight trade-off between the running time of a Shellsort algorithm and the length of the underlying increment sequence. (Update)
Context of citations to this paper: More
.... connected cycles [52] Furthermore, many efforts have produced lower bounds on the depth of shellsort and hypercubic sorting networks [252, 253, 254]. Recently, Cypher and Plaxton have given an involved O(log N loglog N) deterministic sorting algorithm (called sharesort) 55]...
.... sequences, Cypher [6] has established a lower bound of Omega Gamma 1 2 n= lg lg n) Recently, more general lower bounds were shown [16, 18] that hold for arbitrary Shellsort networks and even sequential Shellsort algorithms, thus answering in the negative the longstanding open...
Cited by: More
A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting.. - Plaxton, Suel (Correct)
Packet Routing in Fixed-Connection Networks: A Survey - Grammatikakis, Hsu.. (1998) (Correct)
Similar documents (at the sentence level):
77.8%: Lower Bounds for Shellsort - Plaxton, Suel (1997) (Correct)
65.5%: Routing and Sorting on Fixed Topologies - Suel (1994) (Correct)
64.5%: Improved Lower Bounds for Shellsort - Plaxton, Poonen, Suel (1992) (Correct)
Active bibliography (related documents): More All
1.8: Analysis of Shellsort and Related Algorithms - Sedgewick (1996) (Correct)
0.6: Analysis of Sorting Algorithms by Kolmogorov Complexity - Survey Paul Vit (Correct)
0.5: Best Increments for the Average Case of Shellsort - Ciura (2001) (Correct)
Similar documents based on text: More All
0.4: A Super-Logarithmic Lower Bound for Hypercubic Sorting Networks - Plaxton, Suel (1994) (Correct)
0.4: Lower Bounds for Sorting Networks - Kahale, Leighton, Ma, Plaxton.. (1995) (Correct)
0.4: A Lower Bound for Sorting Networks Based on the Shuffle.. - Plaxton, Suel (1994) (Correct)
Related documents from co-citation: More All
3: Hypercubic sorting networks - Leighton, Plaxton - 1998
3: A lower bound for sorting networks based on the shuffle permutation - Plaxton, Suel - 1994
3: Introduction to Parallel Algorithms and Architectures: Arrays ffl Trees ffl Hype.. (context) - Leighton - 1992
BibTeX entry: (Update)
Plaxton, C. G., and Suel, T. Lower bounds for Shellsort. J. Alg., 23 (2), 1997, pp. 221--240. http://citeseer.comp.nus.edu.sg/654843.html More
@misc{ plaxton97lower,
author = "C. Plaxton and T. Suel",
title = "Lower bounds for Shellsort",
text = "Plaxton, C. G., and Suel, T. Lower bounds for Shellsort. J. Alg., 23 (2),
1997, pp. 221--240.",
year = "1997",
url = "citeseer.comp.nus.edu.sg/654843.html" }
Citations (may not include all citations):2003 The Art of Computer Programming (context) - Knuth - 1973
322 Sorting networks and their applications (context) - Batcher - 1968
110 parallel steps (context) - Ajtai, Koml'os et al. - 1983
70 Average-case analysis of algorithms and data structures - Vitter, Flajolet - 1990
20 A high-speed sorting procedure (context) - Shell - 1959
14 Department of Computer Science (context) - Pratt, Sorting et al. - 1971
13 Improved upper bounds on Shellsort (context) - Incerpi, Sedgewick - 1985
13 Improved lower bounds for Shellsort - Plaxton, Poonen et al. - 1992
12 A lower bound on the size of Shellsort sorting networks (context) - Cypher - 1993
11 Information Processing Letters (context) - Weiss, Sedgewick et al. - 1988
9 A method for information sorting in computer memories (context) - Papernov, Stasevich - 1965
8 An empirical study of minimal storage sorting (context) - Hibbard - 1963
8 The worst case in Shellsort and related algorithms (context) - Poonen - 1993
8 A new upper bound for Shellsort (context) - Sedgewick - 1986
7 Empirical study of the expected running time of Shellsort (context) - Weiss - 1991
6 Practical variations of Shellsort (context) - Incerpi, Sedgewick - 1987
5 A high-speed sorting procedure (context) - Lazarus, Frank - 1960
5 Department of Computer Science (context) - Weiss, for et al. - 1987
5 Journal of Algorithms (context) - Yao, of et al. - 1980
5 An efficient variation of Bubble Sort (context) - Dobosiewicz - 1980
5 Tight lower bounds for Shellsort (context) - Weiss, Sedgewick - 1990
Documents on the same site (http://cis.poly.edu/~suel/papers/papers.htm): More
Theory and Practice of I/O-Efficient Algorithms.. - Arge, Procopiuc.. (1998) (Correct)
A Lower Bound for Sorting Networks Based on the Shuffle.. - Plaxton, Suel (1994) (Correct)
A Super-Logarithmic Lower Bound for Shuffle-Unshuffle Sorting.. - Plaxton, Suel (Correct)
Online articles have much greater impact More about CiteSeer.IST at NUS Add search form to your site Submit documents Feedback
CiteSeer.IST at NUS - Copyright Penn State and NEC. Hosted by the School of Computing, National University of Singapore.