Portal de Periódicos da CAPES

Shellsort with three increments

1997; Wiley; Volume: 10; Issue: 1-2 Linguagem: Inglês

10.1002/(sici)1098-2418(199701/03)10

1098-2418

Svante Janson, Donald E. Knuth,

semigroups and automata theory

Random Structures & AlgorithmsVolume 10, Issue 1-2 p. 125-142 Shellsort with three increments Svante Janson, Svante Janson Department of Mathematics, Uppsala University, P.O. Box 480, 75106 Uppsala, SwedenSearch for more papers by this authorDonald E. Knuth, Corresponding Author Donald E. Knuth Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045Search for more papers by this author Svante Janson, Svante Janson Department of Mathematics, Uppsala University, P.O. Box 480, 75106 Uppsala, SwedenSearch for more papers by this authorDonald E. Knuth, Corresponding Author Donald E. Knuth Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045Computer Science Department, Gates Building 4B, Stanford University, Stanford, CA 94305-9045Search for more papers by this author First published: 13 January 2000 https://doi.org/10.1002/(SICI)1098-2418(199701/03)10:1/2 3.0.CO;2-XCitations: 9AboutPDF ToolsRequest permissionExport citationAdd to favoritesTrack citation ShareShare Give accessShare full text accessShare full-text accessPlease review our Terms and Conditions of Use and check box below to share full-text version of article.I have read and accept the Wiley Online Library Terms and Conditions of UseShareable LinkUse the link below to share a full-text version of this article with your friends and colleagues. Learn more.Copy URL Share a linkShare onFacebookTwitterLinkedInRedditWechat Abstract A perturbation technique can be used to simplify and sharpen A. C. Yao's theorems about the behavior of shellsort with increments (h, g, 1). In particular, when h = θ(n7/15) and g =θ (h1/5), the average running time is O(n23/15). The proof involves interesting properties of the inversions in random permutations that have been h-sorted and g-sorted. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 125–142 (1997) Citing Literature Volume10, Issue1-2January 1997Pages 125-142 RelatedInformation